editor
143
правки
Изменения
Нет описания правки
{{Определение
|definition=
'''Левосторонним выводом слова <tex>\alpha</tex>''' называется такой его вывод такой, что каждая последующая строка получена из предыдущей путем замены самого левого встречающегося в строке нетерминала по одному из правил.
}}
Аналогичным образом определяется ''правосторонний вывод''.
Пусть <tex>\Gamma</tex> - однозначная грамматика. Тогда <tex>\forall \omega \in \mathbb{L}(\Gamma)</tex> у <tex>\omega</tex> существует ровно один левосторонний (правосторонний) вывод.
|proof=
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний вывод. Поскольку каждое слова из языка выводится только одним деревом разбора, то и левосторонний вывод, выводящий это слово, существует только одинлевосторонний вывод этого слова.
}}
== Литература ==
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.
