Изменения
Нет описания правки
# ХМУ 4.2.10, стр 165
# ХМУ 4.2.11, стр 165
# Доказать нерегулярность языка слов $0^n1^n$
# Доказать нерегулярность языка, каждое слово которого содержит поровну 0 и 1.
# Доказать нерегулярность языка палиндромов.
# Доказать нерегулярность языка тандемных повторов.
# Доказать нерегулярность языка $0^n1^m$, $n \le m$
# Доказать нерегулярность языка $0^n1^m$, $n \ne m$
# Доказать нерегулярность языка $0^{n^2}$
# Доказать нерегулярность языка $0^p$, $p$ {{---}} простое
# Доказать нерегулярность языка двоичных записей простых чисел
# Доказать нерегулярность языка $0^n1^m$, $gcd(n, m) = 1$
# Доказать нерегулярность языка $0^a1^b2^c$, $a \ne b$ и $b \ne c$
# Приведите пример нерегулярного языка, для которого выполнена лемма о разрастании
# Доказать, что если состояния $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n)$.
# Предложите алгоритм проверки того, что регулярный язык бесконечен
# Предложите алгоритм проверки того, что регулярный язык является беспрефиксным
# Предложите алгоритм проверки того, что один регулярный язык является подмножеством другого
# Предложите алгоритм проверки того, что регулярные языки не пересекаются
# ХМУ 4.3.1, стр 171.
# ХМУ 4.3.2, стр 171.
# Рассмотрим язык $\{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 $. Докажите, что этот язык регулярный.
# То же, что и предыдущее, только $\{x_{n-1} y_{n-1} z_{n-1} \dots x_1 y_1 z_1 x_0 y_0 z_0 \mid \dots \}$.
# Рассмотрим язык $\{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$. Докажите, что этот язык не является регулярным.
# Рассмотрим отношение на словах $L$: $x \equiv y$, если для любых $u$, $v$ выполнено $uxv \in L \Leftrightarrow uyv \in L$. Классы эквивалентности этого отношения называются синтаксическим моноидом языка $L$. Докажите, что $L$ регулярный тогда и только тогда, когда синтаксический моноид $L$ конечен.
# Придумайте семейство регулярных языков $L_i$, у которых ДКА для $L_i$ содержит $O(i)$ состояний, а синтаксический моноид $L_i$ имеет неполиномиальный размер.
# Постройте КС-грамматику для правильных скобочных последовательностей с двумя типами скобок.
# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей равно числу единиц. Докажите, что ваша грамматика является правильной.
# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей равно удвоенному числу единиц. Докажите, что ваша грамматика является правильной.
# Постройте КС-грамматику для языка $0^k1^n2^{k+n}$.
# Постройте КС-грамматику для языка $0^k1^n2^{k+n}\cup 1^k0^n2^{k+n}$. Сделайте вывод о свойствах КС-языков.
# Постройте КС-грамматику для языка $0^k1^n2^{k+n}1^i0^j2^{i+j}$. Сделайте вывод о свойствах КС-языков.
# Постройте КС-грамматику для языка $0^i1^j2^k$, $i \ne j$ или $j \ne k$.
# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются палиндромами.
# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются правильными скобочными последовательностями.
# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей не равно числу единиц.
# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются тандемными повторами.
# Верно ли, что любую КС-грамматику можно привести к форме, когда любое правило имеет вид $A\to BCD$ или $A\to a$?
# Верно ли, что любой КС-язык над односимвольным алфавитом является регулярным?
</wikitex>
