Изменения
Нет описания правки
# Рассмотрим отношение на словах $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^n1^n$.
# Постройте КС-грамматику для языка слов над алфавитом $\{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$?
# Верно ли, что любой КС-язык над односимвольным алфавитом является регулярным?
# Докажите, что язык не является КС: $0^i1^j2^k$, $i<j<k$.
# Докажите, что язык не является КС: $0^n1^n2^k$, $k<n$.
# Докажите, что язык не является КС: $0^p$, $p$ простое.
# Докажите, что язык двоичных записей простых чисел не является КС.
# Докажите, что язык не является КС: $0^i1^j$, $j=i^2$.
# Докажите, что язык не является КС: $0^n1^n2^k$, $n<k<2n$.
# Докажите, что язык не является КС: $ww^Rw$, $w$ - строка из 0 и 1, $w^R$ - развернутая строка $w$.
# Докажите, что язык $\{0^n1^m2^n3^m\}$ не является КС.
# Докажите, что язык $\{0^n1^m2^n| n \ne m\}$ не является КС.
# Приведите пример не КС-языка, для которого выполнена лемма о разрастании.
# Постройте МП-автомат для языка $0^n1^n$.
# Постройте МП-автомат для языка слов, где число нулей равно числу единиц.
# Постройте МП-автомат для языка $0^n1^{2n}$.
# Постройте МП-автомат для языка $0^n1^m2^{n+m}$.
# Постройте МП-автомат для языка $0^{2n}1^n$.
# Постройте МП-автомат для языка $0^n1^n\cup0^n1^{2n}$.
# Постройте МП-автомат для языка слов $0^n1^m$, где $n \le m \le 2n$.
# Докажите, что для любых $p$ и $q$ существует МП-автомат для языка слов $0^n1^m$, где $n/m=p/q$
# Постройте автомат с магазинной памятью для языка слов над алфавитом $\{0, 1, 2\}$, которые содержат равное число двоек и равное число единиц, или равное число двоек и равное число нулей.
</wikitex>
