63
правки
Изменения
Нет описания правки
{{Определение
|definition=
'''Контекстно-свободной грамматикой''' называется грамматика, у которой в левых частях все всех правил стоят только одиночные нетерминалы.
}}
Язык, задаваемый контекстно-свободной грамматикой называется ''контекстно-свободным языком''.
}}
Крона дерева разбора представляет из себя слово языка, которое выводит это дерево.
{{Определение
|definition=
Грамматика называется однозначной, если у каждого слова имеется не более одного дерева разбора в этой грамматкие.
}}
{{Утверждение
|statement=
Пусть <tex>\Gamma</tex> - однозначная грамматика. Тогда <tex>\forall \omega \in \mathbb{L}(\Gamma)</tex> у <tex>\omega</tex> существует ровно один левосторонний (правосторонний) вывод.
|proof=
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний вывод. Поскольку каждое слова из языка выводится только одним деревом разбора, то и левосторонний вывод, выводящий это слово, существует только один
}}
