137
правок
Изменения
Нет описания правки
==Основные определения==
{{Определение
|id=csgrammar
'''Контекстно-свободный язык''' (англ. ''context-free language'') {{---}} язык, задаваемый контекстно-свободной грамматикой.
}}
==Вывод слова и дерево разбора==
{{Определение
[[Файл:ParsingTree.png|350px]]
==Однозначные грамматики==
{{Определение
|definition=
Грамматика называется '''однозначной''' (англ. ''unambiguous grammar''), если у каждого слова имеется не более одного дерева разбора в этой грамматике.
}}
{{Утверждение
|statement = Грамматика из примера не является однозначной.
|proof =
Выше уже было построено дерево разбора для слова <tex>"(()(()))()"</tex>.
Построим еще одно дерево разбора для данного слова.
Например, оно будет выглядеть так:
Таким образом, существует слово, у которого есть более одного дерева разбора в данной грамматике <tex>\Rightarrow</tex> эта грамматика не является однозначной.
}}
Однако, есть КС-языки, для которых нет однозначных КС-грамматик. Такие языки и грамматики их пораждающие называют [[Существенно неоднозначные языки|''существенно неоднозначными'']].
{{Лемма
* [[Иерархия Хомского формальных грамматик]]
* [[Замкнутость КС-языков относительно различных операций]]
* [[Существенно неоднозначные языки]]
== Литература ==
