Изменения
Нет описания правки
# Существует ли множество натуральных чисел $A$, к которому m-сводится любой множество натуральных чисел?
# Множество называется $m$-полным, если к нему m-сводится любое перечислимое множество. Докажите, что универсальное множество является $m$-полным.
# Докажите, что диагональ универсального множества (множество $\{u | (u, u) \in U\}$ является $m$-полным.# Рассмотрим список слов $A = \{\alpha_1, \alpha_2, \ldots, \alpha_n\}$ над алфавитом $\Sigma$. Введем $n$ новых различных символов $d_1, d_2, \ldots, d_n$. Рассмотрим алфавит $\Sigma' = $\Sigma \cup \{d_1, d_2, \ldots, d_n\}$. Рассмотрим КС-грамматику с одним нетерминалом $S$, алфавитом $\Sigma'$ и $n + 1$ правилом: $S \to \alpha_1 S \d_1$, $S \to \alpha_2 S \d_2$, \dots, $S \to \alpha_n S \d_n$, $S \to \varepsilon$. Язык, порождаемый этой грамматикой, называется языком списка $A$ и обозначается как $L_A$. Опишите все слова языка $L_a$. # Докажите, то проверка грамматики на однозначность является неразрешимой проблемой. Указание: сведите к ней или её дополнению проблему соответствий Поста, используя конструкцию языка списка из предыдущего задания.# Докажите, что для любого списка $A$ дополнение до его языка списка $\overline{L_A}$ является КС-языком. Указание: постройте МП-автомат для $\overline{L_A}$.# Докажите, что проблема проверки пустоты пересечения двух КС-грамматик неразрешима.# Докажите, что проблема проверки эквивалентности двух КС-грамматик неразрешима.# Докажите, что проблема проверки, что язык заданной КС-грамматики совпадает с языком заданного регулярного выражения, неразрешима.# Докажите, что проблема проверки того, что любое слово можно породить в заданной КС-грамматике, неразрешима.# Докажите, что проблема проверки того, что язык одной заданной КС-грамматики входит в язык другой заданной КС-грамматики, неразрешима.# Докажите, что проблема проверки того, что язык заданного регулярного выражения входит в язык заданной КС-грамматики, неразрешима.# Докажите, что проблема проверки того, что язык заданной КС-грамматики содержит палиндром, неразрешима.# Пусть задано два списка $A$ и $B$. Докажите, что $\overline{L_A} \cup \overline{L_B} является регулярным тогда и только тогда, когда он совпадает с $\Sigma'^*$. Следовательно проблема проверки того, что КС-грамматика порождает регулярный язык, неразрешима.# Докажите, что проблема проверки того, что дополнение языка заданной КС-грамматики является КС-языком, неразрешима.
