Упражнения

ᴬ Ответьте на все пункты для следующего ДКА $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). Покажите, что «быть одинакового размера» является отношением эквивалентности.