Изменения
Нет описания правки
# Постройте детерминированный автомат для предыдущего задания или докажите, что в нем слишком много состояний, чтобы его рисовать ;).
# Постройте регулярное выражение для языка слов над бинарным алфавитом, в которых нет двух нулей подряд.
# Построить конечный автомат для языка слов над бинарным алфавитом, в которых которые представляют собой двоичное число 0 кратно , кратное 3.
# ХМУ 4.2.2, стр 163
# ХМУ 4.2.3, стр 163
# Покажите, что следующие три свойства множества $X$ равносильны: (1) $X$ можно представить в виде $A \setminus B$, где $A$ — перечислимое множество, а $B$ — его перечислимое подмножество; (2) $X$ можно представить в виде $A \setminus B$, где $A$ и $B$ — перечислимые множества; (3) $X$ можно представить в виде симметрической разности двух перечислимых множеств.
# Покажите, что множество $X$ можно представить в виде $A\setminus (B\setminus C)$, где $A \supset B \supset C$ — перечислимые множества, если и только если его можно представить в виде симметрической разности (суммы по модулю 2) трёх перечислимых множеств.
# Пусть $A(x,y)$ - вычислимая функция от двух аргументов. Докажите, что для любого $x$ функция $A_x(y)=A(x, y)$ как функция одного аргумента - вычислима.
# Пусть $A(x,y)$ - функция от двух аргументов и для любого $x$ функция $A_x(y)=A(x, y)$ как функция одного аргумента - вычислима. Значит ли это. что функция $A$ вычислима как функция двух аргументов?
# Функция $f$ называется продолжением функции $g$, если для любого $n$, такого что $g$ определена, $f$ также определена и $f(n) = g(n)$. Докажите, что существует вычислимая функция $d(n)$, такая что никакая всюду определенная вычислимая функция $f(n)$ не является ее продолжением.
# Пусть множество пар $A=\{(x, y)\}$ перечислимо. Можно ли утверждать, что множество $B$ минимальных парных для каждого $x$ ($B = \{(x, y)| (x, y) \in A \wedge (x, z)\in A \Rightarrow z \ge y\}$ перечислимо?
# Пусть множество пар $A=\{(x, y)\}$ разрешимо. Можно ли утверждать, что множество $B$ минимальных парных для каждого $x$ ($B = \{(x, y)| (x, y) \in A \wedge (x, z)\in A \Rightarrow z \ge y\}$ перечислимо? Разрешимо?
# Пусть $A$ - произвольный список слов $(a_1, a_2, \ldots, a_n)$ над алфавитом $\Sigma$, содержащем хотя бы 2 символа. Рассмотрим алфавит $\Pi = \Sigma \cup \{1, 2, \ldots, n\}$. Обозначим как $L_A$ язык, содержащий множество слов, порождаемых грамматикой $S\to\varepsilon$, $S\to a_1S1$, ..., $S\to a_n S n$. Докажите, что для любого списка язык $\overline{L_A}$ дополнение до $L_A$ является контекстно-свободным.
# В этой и последующих задачах для задания КС-языка используется некоторая произвольная его КС-грамматика, а для задания регулярного языка - на ваш выбор конечный автомат или регулярное выражение. Докажите, что задача проверки пустоты пересечения контекстно-свободных языков алгоритмически неразрешима.
# Докажите, что задача равенства двух контекстно-свободных языков алгоритмически неразрешима.
# Докажите, что задача проверка равенства заданных контекстно-свободного языка и регулярного языка алгоритмически неразрешима.
# Докажите, что задача проверки равенства КС-языка языку $\Sigma^*$ алгоритмически неразрешима
# Докажите, что задача проверки, что один контекстно-свободный язык является подмножеством другого алгоритмически неразрешима.
# Докажите, что задача проверки, что заданный регулярный язык является подмножеством заданного контекстно-свободного алгоритмически неразрешима.
# Докажите, что множество КС-грамматик, порождающих язык, содержащий хотя бы один палиндром, неразрешимо
# Докажите, что язык $\overline{L_A}\cup\overline{L_B}$ является регулярным тогда и только тогда, когда он совпадает с $\Sigma^*$, то есть соответствующий экземпляр ПСП неразрешим. Сделайте вывод относительно возможности проверки КС-языка на регулярность.
# Докажите, что задача проверки, что дополнение КС-языка является КС-языком, алгоритмически неразрешима
