137
правок
Изменения
Нет описания правки
}}
==Вывод Лево- и правосторонний вывод слова и дерево разбора==
{{Определение
'''Выводом слова''' (англ. ''derivation of a word'') <tex>\alpha</tex> называется последовательность строк, состоящих из терминалов и нетерминалов. Первая строка последовательности состоит из одного стартового нетерминала. Каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, а последней строкой в последовательности является слово <tex>\alpha</tex>.
}}
'''Пример:'''
'''Правосторонним выводом слова''' (англ. '' rightmost derivation'') <tex>\alpha</tex> {{---}} вывод, где каждая последующая строка получена из предыдущей путем замены по одному из правил самого правого встречающегося в строке нетерминала.
}}
Рассмотрим левосторонний вывод скобочной последовательности из примера:<br>
<tex>\boldsymbol{S}\Rightarrow (\boldsymbol{S})S \Rightarrow ((\boldsymbol{S})S)S\Rightarrow (()\boldsymbol{S})S\Rightarrow(()\boldsymbol{S}(S))S\Rightarrow(()(\boldsymbol{S}))S\Rightarrow(()(\boldsymbol{S}(S)))S\Rightarrow(()((\boldsymbol{S})))S\Rightarrow(()(()))\boldsymbol{S}\Rightarrow(()(()))(\boldsymbol{S})S\Rightarrow(()(()))()\boldsymbol{S}\Rightarrow(()(()))()</tex>
==Дерево разбора==
{{Определение
==Однозначные грамматики==
{{Определение
|definition=
}}
{{Лемма
|id=lemma-
|statement=
Пусть <tex>\Gamma</tex> {{---}} однозначная грамматика. Тогда <tex>\forall \omega \in \mathbb{L}(\Gamma)</tex> существует ровно один левосторонний (правосторонний) вывод.
|proof=
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний(правосторонний) вывод. Поскольку каждое слово из языка выводится только одним деревом разбора, то существует только один левосторонний(правосторонний) вывод этого слова.
}}
<br>
{{Утверждение
|statement = Грамматика из примера не является однозначной.
Таким образом, существует слово, у которого есть более одного дерева разбора в данной грамматике <tex>\Rightarrow</tex> эта грамматика не является однозначной.
}}
<br>
Для одного и того же языка может существовать как однозначная, так и неоднозначная грамматика.
Например, у языка правильных скобочных последовательностей существует однозначная грамматика.
}}
<br>
Однако, есть КС-языки, для которых не существует однозначных КС-грамматик. Такие языки и грамматики их порождающие называют [[Существенно неоднозначные языки|''существенно неоднозначными'']].
==См. также==
