Список заданий по ТФЯ 2015

<wikitex>

Теория формальных языков, 5 семестр

1. Построить конечный автомат для языка слов над бинарным алфавитом, в которых четность числа 0 равна четности числа 1
2. Построить конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3
3. Построить конечный автомат для языка слов над бинарным алфавитом, в которых нет трех нулей подряд
4. Построить конечный автомат для языка слов над бинарным алфавитом, которые представляют собой двоичную запись чисел, кратных 5
5. Построить конечный автомат для языка слов над бинарным алфавитом, в которых число нулей не кратно 3
6. Построить конечный автомат для языка слов над бинарным алфавитом, в которых есть три нуля подряд. Сделайте вывод из последних двух заданий.
7. Построить конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3 и которые представляют собой двоичную запись чисел кратных 5.
8. Построить конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3 или которые представляют собой двоичную запись чисел кратных 5. Сделайте вывод из последних двух заданий.
9. Построить конечный автомат для языка слов над бинарным алфавитом, в пятый символ с конца - 0. Можно построить недетерминированный автомат.
10. Постройте детерминированный автомат для предыдущего задания или докажите, что в нем слишком много состояний, чтобы его рисовать ;).
11. Постройте регулярное выражение для языка слов над бинарным алфавитом, в которых нет двух нулей подряд.
12. Построить конечный автомат для языка слов над бинарным алфавитом, которые представляют собой двоичное число, кратное 3.
13. ХМУ 4.2.2, стр 163
14. ХМУ 4.2.3, стр 163
15. ХМУ 2.3.1, стр 83
16. Докажите, что минимальный ДКА для языка $(0|1)^*0(0|1)^k$ содержит минимум $2^k$ состояний
17. ХМУ 4.2.4, стр 163
18. ХМУ 4.2.5, стр 164
19. ХМУ 4.2.6, стр 164
20. ХМУ 4.2.7, стр 164
21. ХМУ 4.2.8, стр 164
22. ХМУ 4.2.10, стр 165
23. ХМУ 4.2.11, стр 165
24. Доказать нерегулярность языка слов $0^n1^n$
25. Доказать нерегулярность языка, каждое слово которого содержит поровну 0 и 1.
26. Доказать нерегулярность языка палиндромов.
27. Доказать нерегулярность языка тандемных повторов.
28. Доказать нерегулярность языка $0^n1^m$, $n \le m$
29. Доказать нерегулярность языка $0^n1^m$, $n \ne m$
30. Доказать нерегулярность языка $0^{n^2}$
31. Доказать нерегулярность языка $0^p$, $p$ — простое
32. Доказать нерегулярность языка двоичных записей простых чисел
33. Доказать нерегулярность языка $0^n1^m$, $gcd(n, m) = 1$
34. Доказать нерегулярность языка $0^a1^b2^c$, $a \ne b$ и $b \ne c$
35. Приведите пример нерегулярного языка, для которого выполнена лемма о разрастании
36. Доказать, что если состояния $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n)$.
37. Предложите алгоритм проверки того, что регулярный язык бесконечен
38. Предложите алгоритм проверки того, что регулярный язык является беспрефиксным
39. Предложите алгоритм проверки того, что один регулярный язык является подмножеством другого
40. Предложите алгоритм проверки того, что регулярные языки не пересекаются
41. ХМУ 4.3.1, стр 171.
42. ХМУ 4.3.2, стр 171.
43. Рассмотрим язык $\{x_0 y_0 z_0 x_1 y_1 z_1 \dots x_{n-1} y_{n-1} z_{n-1} \mid x_i, y_i, z_i \in \{0, 1\}\}$, где $ X = x_{n-1}x_{n-2}\dots x_0$ и аналогично представляется $Y$ и $Z$, причем $ X + Y = Z $. Докажите, что этот язык регулярный.
44. То же, что и предыдущее, только $\{x_{n-1} y_{n-1} z_{n-1} \dots x_1 y_1 z_1 x_0 y_0 z_0 \mid \dots \}$.
45. Рассмотрим язык $\{x_0 y_0 z_0 x_1 y_1 z_1 \dots x_{n-1} y_{n-1} z_{n-1} \mid x_i, y_i, z_i \in \{0, 1\}\}$, где $X = x_{n-1}x_{n-2}\dots x_0$ и аналогично представляется $Y$ и $Z$, причем $X \times Y = Z$. Докажите, что этот язык не является регулярным.
46. Рассмотрим отношение на словах $L$: $x \equiv y$, если для любых $u$, $v$ выполнено $uxv \in L \Leftrightarrow uyv \in L$. Классы эквивалентности этого отношения называются синтаксическим моноидом языка $L$. Докажите, что $L$ регулярный тогда и только тогда, когда синтаксический моноид $L$ конечен.
47. Придумайте семейство регулярных языков $L_i$, у которых ДКА для $L_i$ содержит $O(i)$ состояний, а синтаксический моноид $L_i$ имеет неполиномиальный размер.
48. Постройте КС-грамматику для правильных скобочных последовательностей с двумя типами скобок.
49. Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей равно числу единиц. Докажите, что ваша грамматика является правильной.
50. Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей равно удвоенному числу единиц. Докажите, что ваша грамматика является правильной.
51. Постройте КС-грамматику для языка $0^k1^n2^{k+n}$.
52. Постройте КС-грамматику для языка $0^k1^n2^{k+n}\cup 1^k0^n2^{k+n}$. Сделайте вывод о свойствах КС-языков.
53. Постройте КС-грамматику для языка $0^k1^n2^{k+n}1^i0^j2^{i+j}$. Сделайте вывод о свойствах КС-языков.
54. Постройте КС-грамматику для языка $0^i1^j2^k$, $i \ne j$ или $j \ne k$.
55. Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются палиндромами.
56. Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются правильными скобочными последовательностями.
57. Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей не равно числу единиц.
58. Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются тандемными повторами.
59. Верно ли, что любую КС-грамматику можно привести к форме, когда любое правило имеет вид $A\to BCD$ или $A\to a$?
60. Верно ли, что любой КС-язык над односимвольным алфавитом является регулярным?
61. ХМУ 7.2.1 (а)
62. ХМУ 7.2.1 (б)
63. ХМУ 7.2.1 (в)
64. ХМУ 7.2.1 (г)
65. ХМУ 7.2.1 (д)
66. ХМУ 7.2.1 (е)
67. ХМУ 7.2.5 (а)
68. ХМУ 7.2.5 (б)
69. Докажите, что язык $\{0^n1^m2^n3^m\}$ не является КС.
70. Докажите, что язык $\{0^n1^m2^n| n \ne m\}$ не является КС.
71. Приведите пример не КС-языка, для которого выполнена лемма о разрастании.
72. Постройте МП-автомат для языка $0^n1^n$.
73. Постройте МП-автомат для языка слов, где число нулей равно числу единиц.
74. Постройте МП-автомат для языка $0^n1^{2n}$.
75. Постройте МП-автомат для языка $0^n1^m2^{n+m}$.
76. Постройте МП-автомат для языка $0^{2n}1^n$.
77. Постройте МП-автомат для языка $0^n1^n\cup0^n1^{2n}$.
78. Постройте МП-автомат для языка слов $0^n1^m$, где $n \le m \le 2n$.
79. Докажите, что для любых $p$ и $q$ существует МП-автомат для языка слов $0^n1^m$, где $n/m=p/q$
80. Постройте автомат с магазинной памятью для языка слов над алфавитом $\{0, 1, 2\}$, которые содержат равное число двоек и равное число единиц, или равное число двоек и равное число нулей.
81. Существует ли для языка из предыдущего задания детерминированный автомат?
82. Постройте автомат с магазинной памятью для языка палиндромов.
83. Докажите, что для любого автомата с магазинной памятью существует эквивалентный, который на каждом переходе кладет в стек не более 2 символов. Ваша конструкция должна сохранять детерминированность автомата, если ранее он был детерминированным.
84. Докажите, что для любого детерминированного автомата с магазинной памятью существует эквивалентный, который при $\varepsilon$-переходе только снимает или заменяет верхний символ стека (то есть размер стека не увеличивается на $\varepsilon$-переходах).
85. Рассмотрим детерминированный автомат с магазинной памятью, для которого выполнены свойства из двух предыдущих заданий. Докажите, что для любого состояния $p$ автомата и строки $\gamma$ в стеке существует строка $s$, для которой выполняется следующее свойство. Начав в состоянии $p$ и со стеком $\gamma$, считав строку $s$ автомат переходит некоторое состояние $q$ и имеет в стеке $\beta$, причем какую бы строку далее автомат не получил на вход, на вершине стека никогда не окажется второй символ $\beta$.
86. На основании трех предыдущих заданий докажите, что не существует детерминированного автомата с магазинной памятью для языка палиндромов.
87. Докажите, что объединение и пересечение разрешимых языков разрешимо.
88. Докажите, что объединение и пересечение перечислимых языков перечислимо.
89. Докажите, что конкатенация и замыкание Клини разрешимых языков разрешимы.
90. Докажите, что конкатенация и замыкание Клини перечислимых языков перечислимы.
91. Докажите, что если множества $A$ и $B$ разрешимы (перечислимы), то их декартово произведение перечислимо.
92. Докажите, что образ перечислимого множества под действием вычислимой (не обязательно всюду определенной) функции перечислим.
93. Докажите, что прообраз перечислимого множества под действием вычислимой (не обязательно всюду определенной) функции перечислим.
94. Теорема об униформизации. Пусть задано перечислимое множество пар $F$. Докажите, что найдется вычислимая функция $f$, такая что для любого $x$, для которого существует $y$, такой что $(x,y)\in F$ выполнено, что $(x, f(x)) \in F$.
95. Пусть даны два перечислимых множества $X$ и $Y$. Докажите, что существуют непересекающиеся перечислимые множества $X' \subset X$ и $Y' \subset Y$, такие что $X' \cup Y' = X \cup Y$.
96. Докажите, что множество чисел $i$, таких, что в десятичной записи числа $\pi$ встречается последовательность из $i$ семерок подряд, перечислимо. Является ли оно разрешимым? Почему?
97. Докажите, что множество чисел $i$, таких, что в десятичной записи числа $\pi$ как подстрока десятичная запись $i$, перечислимо. Можно ли привести тот же аргумент, что и в предыдущем задании, для доказательства его (не)разрешимости?
98. Докажите, что любое бесконечное перечислимое множество содержит бесконечное разрешимое подмножество.
99. Пусть $f$ - вычислимая функция. Докажите, что существует вычислимая функция $g$ с областью определения, совпадающей с областью значений $f$, такая что $f(g(f(x))) = f(x)$ для любого $x$, на котором $f$ определена.
100. Вещественное число $\alpha$ называется вычислимым, если существует вычислимая функция $a$, которая по любому рациональному $\varepsilon > 0$ даёт рациональное приближение к $\alpha$ с ошибкой не более $\varepsilon$, то есть $|\alpha-a(\varepsilon)| \le \varepsilon$ для любого рационального $\varepsilon > 0$. Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда множество рациональных чисел, меньших $\alpha$, разрешимо
101. Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда последовательность знаков представляющей его десятичной (или двоичной) дроби вычислима.
102. Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к $\alpha$ (то есть является вычислимой функция, которая по $\varepsilon$ возвращает $n_0$, такое что $|a_n - \alpha| \le \varepsilon$ для $n > n_0$)
103. Покажите, что сумма, произведение, разность и частное вычислимых действительных чисел вычислимы. Покажите, что корень многочлена с вычислимыми коэффициентами вычислим.
104. Сформулируйте и докажите утверждение о том, что предел вычислимо сходящейся последовательности вычислимых действительных чисел вычислим.
105. Вещественное число $\alpha$ называют перечислимым снизу, если множество всех рациональных чисел, меньших $\alpha$, перечислимо. Перечислимость сверху определяется аналогично. Докажите, что число $\alpha$ перечислимо снизу тогда и только тогда, когда оно является пределом некоторой вычислимой возрастающей последовательности рациональных чисел.
106. Докажите, что вещественное число вычислимо тогда и только тогда, когда оно перечислимо снизу и сверху.
107. Покажите, что следующие три свойства множества $X$ равносильны: (1) $X$ можно представить в виде $A \setminus B$, где $A$ — перечислимое множество, а $B$ — его перечислимое подмножество; (2) $X$ можно представить в виде $A \setminus B$, где $A$ и $B$ — перечислимые множества; (3) $X$ можно представить в виде симметрической разности двух перечислимых множеств.
108. Покажите, что множество $X$ можно представить в виде $A\setminus (B\setminus C)$, где $A \supset B \supset C$ — перечислимые множества, если и только если его можно представить в виде симметрической разности (суммы по модулю 2) трёх перечислимых множеств.
109. Пусть $A(x,y)$ - вычислимая функция от двух аргументов. Докажите, что для любого $x$ функция $A_x(y)=A(x, y)$ как функция одного аргумента - вычислима.
110. Пусть $A(x,y)$ - функция от двух аргументов и для любого $x$ функция $A_x(y)=A(x, y)$ как функция одного аргумента - вычислима. Значит ли это. что функция $A$ вычислима как функция двух аргументов?
111. Функция $f$ называется продолжением функции $g$, если для любого $n$, такого что $g$ определена, $f$ также определена и $f(n) = g(n)$. Докажите, что существует вычислимая функция $d(n)$, такая что никакая всюду определенная вычислимая функция $f(n)$ не является ее продолжением.
112. Пусть множество пар $A=\{(x, y)\}$ перечислимо. Можно ли утверждать, что множество $B$ минимальных парных для каждого $x$ ($B = \{(x, y)| (x, y) \in A \wedge (x, z)\in A \Rightarrow z \ge y\}$ перечислимо?
113. Пусть множество пар $A=\{(x, y)\}$ разрешимо. Можно ли утверждать, что множество $B$ минимальных парных для каждого $x$ ($B = \{(x, y)| (x, y) \in A \wedge (x, z)\in A \Rightarrow z \ge y\}$ перечислимо? Разрешимо?
114. Пусть $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$ является контекстно-свободным.
115. В этой и последующих задачах для задания КС-языка используется некоторая произвольная его КС-грамматика, а для задания регулярного языка - на ваш выбор конечный автомат или регулярное выражение. Докажите, что задача проверки пустоты пересечения контекстно-свободных языков алгоритмически неразрешима.
116. Докажите, что задача равенства двух контекстно-свободных языков алгоритмически неразрешима.
117. Докажите, что задача проверка равенства заданных контекстно-свободного языка и регулярного языка алгоритмически неразрешима.
118. Докажите, что задача проверки равенства КС-языка языку $\Sigma^*$ алгоритмически неразрешима
119. Докажите, что задача проверки, что один контекстно-свободный язык является подмножеством другого алгоритмически неразрешима.
120. Докажите, что задача проверки, что заданный регулярный язык является подмножеством заданного контекстно-свободного алгоритмически неразрешима.
121. Докажите, что множество КС-грамматик, порождающих язык, содержащий хотя бы один палиндром, неразрешимо
122. Докажите, что язык $\overline{L_A}\cup\overline{L_B}$ является регулярным тогда и только тогда, когда он совпадает с $\Sigma^*$, то есть соответствующий экземпляр ПСП неразрешим. Сделайте вывод относительно возможности проверки КС-языка на регулярность.
123. Докажите, что задача проверки, что дополнение КС-языка является КС-языком, алгоритмически неразрешима