59
правок
Изменения
→Однозначные грамматики
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний(правосторонний) вывод. Поскольку каждое слово из языка выводится только одним деревом разбора, то существует только один левосторонний(правосторонний) вывод этого слова.
}}
{{Утверждение
|statement = Грамматика из примера не является однозначной.|proof =Выше уже было построено дерево разбора для слова <tex>"(()(()))()"</tex>.
Построим еще одно дерево разбора для данного слова.
Таким образом, существует слово, у которого есть более одного дерева разбора в данной грамматике <tex>\Rightarrow</tex> эта грамматика не является однозначной.
}}
{{Утверждение
|statement = Существуют языки, которые можно задать одновременно как однозначными, так и неоднозначными грамматиками.|proof =Для доказательства достаточно привести однозначную грамматику для языка правильных скобочных последовательностей (неоднозначной грамматикой для данного языка является грамматика из примера выше).
Рассмотрим грамматику:
