Изменения
Нет описания правки
# Рассмотрим язык $\{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$. Докажите, что этот язык не является регулярным.
# Из алгоритма построения множества различимых состояний следует, что $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n^2)$. Докажите, что если состояния $u$ и $v$ автомата различимы, то $u$ и $v$ различимы строкой длины $O(n)$.
# Постройте КС-грамматику для правильных скобочных последовательностей с двумя типами скобок. В этом и следующих заданиях, после разработки КС грамматики необходимо выбрать в качестве примера слово и продемонстрировать его левосторонний вывод и дерево разбора.
# Постройте КС-грамматику для языка $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}$. Сделайте вывод про КС языки.
# Пусть задана КС-грамматика для языка $L$. Укажите, как построить КС-грамматику для языка $L^*$.
# Пусть задана КС-грамматика для языка $L$. Обозначим как $L^R$ язык, составленный из слов, которые, если их прочитать от конца к началу, принадлежат языку $L$. Укажите, как построить КС-грамматику для языка $L^R$.
# Постройте КС-грамматику для языка $0^i1^j2^k$, $i \ne j$ или $j \ne k$.
# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются палиндромами.
# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются правильными скобочными последовательностями.
# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, в которых число нулей не равно числу единиц.
# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются тандемными повторами (не имеют вид $xx$ для некоторого слова $x$).
# Постройте КС-грамматику, описывающие академические регулярные выражения над алфавитом $\{0, 1\}$.
# КС грамматика называется линейной, если в правых частях правил встречается максимум один нетерминал. Праволинейные грамматики, в которых этот нетерминал находится на последнем месте, порождают регулярные языки. Приведите пример линейной грамматики, которая порождает нерегулярный язык.
# КС грамматика называется леволинейной, если в правых частях правил встречается максимум один нетерминал, причем если он есть, то находится на первом месте. Докажите, что язык можно породить леволинейной грамматикой тогда и только тогда, когда он регулярный."
