244
правки
Изменения
Нет описания правки
# КС грамматика называется леволинейной, если в правых частях правил встречается максимум один нетерминал, причем если он есть, то находится на первом месте. Докажите, что язык можно породить леволинейной грамматикой тогда и только тогда, когда он регулярный.
# КС грамматика называется смешанной линейной, если в правых частях правил встречается максимум один нетерминал, причем если он есть, то находится либо на первом, либо на последнем месте. Докажите, что существует КС язык, не являющийся регулярным, который можно породить смешанной линейной грамматикой.
# Постройте МП-автомат для языка слов, где число нулей равно числу единиц.
# Постройте МП-автомат для языка $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$.
# Постройте автомат с магазинной памятью для языка слов над алфавитом $\{0, 1, 2\}$, которые содержат равное число двоек и равное число единиц, или равное число двоек и равное число нулей.
# Верно ли, что любую КС-грамматику можно привести к форме, когда любое правило имеет вид $A\to BCD$ или $A\to a$?
# Предложите алгоритм проверки, что в грамматике выводится хотя бы одно слово.
# Предложите алгоритм нахождения слова минимальной длины, выводящегося в заданной грамматике.
# Грамматика называется леворекурсивной, если найдется такой нетерминал A, что за один или более шаг из A можно вывести строку, которая начинается с A ($A \Rightarrow^+ A\alpha$). Предложите алгоритм, который проверяет, является ли грамматика леворекурсивной.
# Предложите алгоритм проверки, что в заданная КС грамматика в НФХ порождает конечное число слов.
# Предложите алгоритм, который, получает на вход КС грамматику в НФХ, про которую с помощью алгоритма из предыдущего задания выяснили, что она порождает конечное число слов. На выход необходимо выдать самое длинное слово, которое порождается этой КСГ.
# Билл поменял местами шаги алгоритма приведения КСГ к НФХ: он сначала удаляет цепные правила, а затем eps-правила. Будет ли корректно работать алгоритм?
# Билл поменял местами шаги алгоритма приведения КСГ к НФХ: он сначала удаляет eps-правила, а затем длинные правые части. Можно ли поправить алгоритм удаления eps-правил, чтобы он работал с длинными правыми частями? Чем эта версия алгоритма хуже оригинальной?
# Алиса разработала свою нормальную форму грамматики, в которой каждое правило имеет вид $A \to BCD$, $A \to BC$ или $A \to c$. Как обобщить алгоритм КЯК на грамматики в такой форме? Сравните получившийся алгоритм с оригинальным.
# Алиса разработала свою нормальную форму грамматики, в которой каждое правило имеет вид $A \to BC$, $A \to B$ или $A \to c$. Как обобщить алгоритм КЯК на грамматики в такой форме? Сравните получившийся алгоритм с оригинальным.
# Рассмотрим дерево разбора некоторого слова в грамматике в НФХ. Как соотносятся количество нетерминалов и терминалов в дереве?
