Изменения

# ДокажитеИз алгоритма построения множества различимых состояний следует, что если состояния $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n^2)$.# Докажите, что если состояния $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n)$.# Предложите алгоритм проверки того, что регулярный язык бесконечен# Предложите алгоритм подсчёта числа слов в регулярном языке (если язык бесконечен, алгоритм должен выдать информацию, что он бесконечен). Алгоритм должен работать за полином от числа состояний в автомате.# Предложите алгоритм проверки того, что регулярный язык является беспрефиксным# Предложите алгоритм проверки того, что один регулярный язык является подмножеством другого# Предложите алгоритм проверки того, что регулярные языки не пересекаются# Предложите алгоритм проверки того, что объединение двух заданных регулярных языков совпадет с некоторым третьим заданным.# Приведите пример регулярного языка и двух неизоморфных недетерминированных автоматов для него, которые при этом имеют минимальное число состояний среди всех недетерминированных автоматов для этого языка.# Рассмотрим язык $\{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^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\}$, которые содержат равное число двоек и равное число единиц, или равное число двоек и равное число нулей.