Изменения
Нет описания правки
# Алиса разработала свою нормальную форму грамматики, в которой каждое правило имеет вид $A \to BC$, $A \to B$ или $A \to c$. Как обобщить алгоритм КЯК на грамматики в такой форме? Сравните получившийся алгоритм с оригинальным.
# Рассмотрим дерево разбора некоторого слова в грамматике в НФХ. Как соотносятся количество нетерминалов и терминалов в дереве?
# Докажите, что язык не является КС: $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\}$ не является КС.
# Верно ли, что любой КС-язык над односимвольным алфавитом является регулярным?
# Рассмотрим несколько неправильных модификаций леммы о разрастании для КС-языков. Для каждой модификации придумайте КС-язык, который не удовлетворяет этой лемме. Для КС-языка $L$ существует число $n$, что любое слово $w \in L$, $|w| \ge n$ можно разбить на четыре части $w = uvyz$, где $|vy| \le n$, $vy \neq \varepsilon$ что для любого $k \ge 0$, $uv^ky^kz \in L$.
# Для КС-языка $L$ существует число $n$, что любое слово $w \in L$, $|w| \ge n$ можно разбить на четыре части $w = vxyz$, где $|vxy| \le n$, $vy \neq \varepsilon$, что для любого $k \ge 0$, $v^kxy^kz \in L$.
# Докажите, что следующая модификация леммы о разрастании верна: Для КС-языка $L$ существует число $n$, что любое слово $w \in L$, $|w| \ge n$ можно разбить на пять частей $w = uvxyz$, где $|vxy| \le n$, $v \neq \varepsilon$, $y \neq \varepsilon$ что для любого $k \ge 0$, $v^kxy^kz \in L$.
