Разрешимость

ᴬ Ответьте на все пункты для следующего ДКА $M$ и обоснуйте свои ответы.

Рассмотрим задачу определения того, эквивалентны ли ДКА и регулярное выражение. Представьте эту задачу как язык и покажите, что он разрешим.

Пусть $\operatorname {ALL}_{\text{DFA }}=\left\{ \langle A\rangle \mid A \text{ — ДКА и } L(A)=\Sigma^{*}\right\}$. Покажите, что $\operatorname {ALL}_{\text{DFA }}$ разрешим.

Пусть $A \varepsilon_{\mathrm{CFG}}=\left\{ \langle G\rangle \mid G\text{ — КС-грамматика, порождающая }\varepsilon \right\}$. Покажите, что $A \varepsilon_{\mathrm{CFG}}$ разрешим.

ᴬ Пусть $E_{\mathrm{TM}}=\left\{ \langle M\rangle \mid M\text{ — МТ и }L(M)=\emptyset \right\}$. Покажите, что $\overline{E_{\mathrm{TM}}}$ — дополнение $E_{\mathrm{TM}}$ — распознаётся машиной Тьюринга.

Пусть $X$ — множество $\left\{ 1,2,3,4,5\right\}$, а $Y$ — множество $\left\{ 6,7,8,9,10\right\}$. Опишем функции $f: X \longrightarrow Y$ и $g: X \longrightarrow Y$ в следующих таблицах. Ответьте на каждый пункт и обоснуйте каждый отрицательный ответ.

Пусть $\mathcal{B}$ — множество всех бесконечных последовательностей над $\left\{ 0,1\right\}$. Покажите, что $\mathcal{B}$ несчётно, используя доказательство методом диагонализации.

Пусть $T=\left\{ (i, j, k) \mid i, j, k \in \mathcal{N}\right\}$. Покажите, что $T$ счётно.

Вспомните, как мы определяем «одинаковый размер» множеств в определении 4.12 (стр. 203). Покажите, что «быть одинакового размера» является отношением эквивалентности.

ᴬ Пусть INFINITE $_{\text{DFA }}=\left\{ \langle A\rangle \mid A\text{ — ДКА и }L(A)\text{ — бесконечный язык}\right\}$. Покажите, что INFINITE $_{\text{DFA }}$ разрешим.

Пусть $I N F I N I T E_{\text{PDA }}=\left\{ \langle M\rangle \mid M\text{ — МП-автомат и }L(M)\text{ — бесконечный язык}\right\}$. Покажите, что INFINITE ${ }_{\text{PDA }}$ разрешим.

ᴬ Пусть $A=\left\{ \langle M\rangle \mid M\text{ — ДКА, не допускающий ни одной строки, содержащей нечётное число единиц}\right\}$. Покажите, что $A$ разрешим.

Пусть $A=\left\{ \langle R, S\rangle \mid R\text{ и }S\text{ — регулярные выражения и }L(R) \subseteq L(S)\right\}$. Покажите, что $A$ разрешим.

ᴬ Пусть $\Sigma =\left\{ 0,1\right\}$. Покажите, что задача определения того, порождает ли КС-грамматика хотя бы одну строку из $1^{*}$, разрешима. Иными словами, покажите, что

— разрешимый язык.

• Покажите, что задача определения того, порождает ли КС-грамматика все строки из $1^{*}$, разрешима. Иными словами, покажите, что $\left\{ \langle G\rangle \mid G \text{ — КС-грамматика над } \left\{ 0,1\right\} \text{ и } 1^{*} \subseteq L(G)\right\}$ — разрешимый язык.

Пусть $A=\left\{ \langle R\rangle \mid R\text{ — регулярное выражение, описывающее язык, содержащий хотя бы одну строку }w\text{ с подстрокой 111 (то есть }w=x 111 y\text{ для некоторых }x\text{ и }y\text{)}\right\}$. Покажите, что $A$ разрешим.

Докажите, что $E Q_{\text{DFA }}$ разрешим, проверяя оба ДКА на всех строках до некоторого размера. Вычислите размер, при котором это работает.

• Пусть $C$ — язык. Докажите, что $C$ распознаётся машиной Тьюринга тогда и только тогда, когда существует разрешимый язык $D$, такой что $C=\left\{ x \mid \exists y(\langle x, y\rangle \in D)\right\}$.

• Докажите, что класс разрешимых языков не замкнут относительно гомоморфизма.

Пусть $A$ и $B$ — два непересекающихся языка. Будем говорить, что язык $C$ разделяет $A$ и $B$, если $A \subseteq C$ и $B \subseteq \bar{C}$. Покажите, что любые два непересекающихся ко-распознаваемых языка можно разделить некоторым разрешимым языком.

Пусть $S=\left\{ \langle M\rangle \mid M \text{ — ДКА, допускающий } w^{\mathcal{R}} \text{ всякий раз, когда он допускает } w\right\}$. Покажите, что $S$ разрешим.

Пусть $P R E F I X-F R E E_{\text{REX }}=\left\{ \langle R\rangle \mid R\text{ — регулярное выражение и }L(R)\text{ беспрефиксен}\right\}$. Покажите, что PREFIX-FREE ${ }_{\text{REX }}$ разрешим. Почему аналогичный подход не позволяет показать, что PREFIX-FREE ${ }_{\mathrm{CFG}}$ разрешим?

• ᴬ Будем говорить, что НКА неоднозначен, если он допускает некоторую строку по двум разным вычислительным ветвям. Пусть $A M B I G_{\text{NFA }}=\left\{ \langle N\rangle \mid N\text{ — неоднозначный НКА}\right\}$. Покажите, что $A M B I G_{\text{NFA }}$ разрешим. (Подсказка: один изящный способ решить эту задачу — построить подходящий ДКА, а затем применить к нему $E_{\text{DFA }}$.)

Бесполезное состояние в автомате с магазинной памятью — это состояние, в которое ни при каком входе никогда не попадают. Рассмотрим задачу определения того, есть ли у автомата с магазинной памятью бесполезные состояния. Сформулируйте эту задачу как язык и покажите, что она разрешима.

• ᴬ Пусть $B A L_{\text{DFA }}=\left\{ \langle M\rangle \mid M\text{ — ДКА, допускающий некоторую строку с поровну нулей и единиц}\right\}$. Покажите, что $B A L_{\text{DFA }}$ разрешим. (Подсказка: здесь полезны теоремы о КС-языках.)

• Пусть $P A L_{\text{DFA }}=\left\{ \langle M\rangle \mid M\text{ — ДКА, допускающий некоторый палиндром}\right\}$. Покажите, что $P A L_{\text{DFA }}$ разрешим. (Подсказка: здесь полезны теоремы о КС-языках.)

• Пусть $E=\left\{ \langle M\rangle \mid M\text{ — ДКА, допускающий некоторую строку с бо́льшим числом единиц, чем нулей}\right\}$. Покажите, что $E$ разрешим. (Подсказка: здесь полезны теоремы о КС-языках.)

Пусть $C=\left\{ \langle G, x\rangle \mid G\text{ — КС-грамматика, }x\text{ — подстрока некоторой строки }y \in L(G)\right\}$. Покажите, что $C$ разрешим. (Подсказка: изящное решение этой задачи использует разрешающую машину для $E_{\text{CFG }}$.)

Пусть $C_{\text{CFG }}=\left\{ \langle G, k\rangle \mid G\text{ — КС-грамматика и }L(G)\text{ содержит ровно }k\text{ строк, где }k \geq 0\text{ или }k=\infty \right\}$. Покажите, что $C_{\mathrm{CFG}}$ разрешим.

Пусть $A$ — распознаваемый машиной Тьюринга язык, состоящий из описаний машин Тьюринга, $\left\{ \left\langle M_{1}\right\rangle ,\left\langle M_{2}\right\rangle , \ldots \right\}$, где каждая $M_{i}$ является разрешающей машиной. Докажите, что существует разрешимый язык $D$, который не разрешается ни одной разрешающей машиной $M_{i}$, чьё описание входит в $A$. (Подсказка: может быть полезно рассмотреть перечислитель для $A$.)

Будем говорить, что переменная $A$ в КС-языке $G$ полезна, если она встречается в некотором выводе некоторой строки $w \in G$. По данным КС-грамматике $G$ и переменной $A$ рассмотрим задачу проверки того, является ли $A$ полезной. Сформулируйте эту задачу как язык и покажите, что она разрешима.

В доказательстве леммы 2.41 говорится, что $(q, x)$ — зацикливающая ситуация для ДМП-автомата $P$, если, будучи запущенным в состоянии $q$ с $x \in \Gamma$ на вершине стека, он никогда не опускает стек ниже $x$ и никогда не читает входной символ. Покажите, что $F$ разрешим, где $F=\left\{ \langle P, q, x\rangle \mid (q, x)\text{ — зацикливающая ситуация для }P\right\}$.