Изменения

Перейти к: навигация, поиск
Нет описания правки
|id=csgrammar
|definition=
'''Контекстно-свободной грамматикой''' (англ. ''сontext-free grammar'') называется грамматика, у которой в левых частях всех правил стоят только одиночные нетерминалы. <br>Язык, задаваемый контекстно}}{{Определение|definition='''Контекстно-свободной грамматикой называется свободный язык'''(англ. ''контекстноcontext-свободным языком'free language'') {{---}} язык, задаваемый контекстно-свободной грамматикой.
}}
{{Определение
|definition=
'''Выводом слова''' <tex>\alpha</tex> называется последовательность строк, состоящих из терминалов и нетерминалов, где первой идет . Первая строка, состоящая последовательности состоит из одного стартового нетерминала, а каждая . Каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, и а последней строкой в последовательности является слово <tex>\alpha</tex>.
}}
Рассмотрим на примере грамматики, выводящей все правильные скобочные последовательности.  Терминальные символы {{---}} <tex>"(" </tex> и <tex>")", нетерминал </tex>;  <tex>S</tex>, он же {{---}} стартовый нетерминал, правила;  Правила:<br>
<tex>S\rightarrow (S)S</tex><br>
<tex>S\rightarrow S(S)</tex><br>
<tex>S\rightarrow \varepsilon</tex><br>
Выведем слово <tex>"(()(()))()"</tex>:<br><tex>\boldsymbol{S}\rightarrow Rightarrow (S)\boldsymbol{S} \rightarrow Rightarrow (S)(\boldsymbol{S})S\rightarrowRightarrow(S)()\boldsymbol{S}\rightarrowRightarrow(\boldsymbol{S})()\rightarrowRightarrow(\boldsymbol{S}(S))()\rightarrowRightarrow(S(S)(\boldsymbol{S}))()\rightarrowRightarrow(S(S)(\boldsymbol{S}(S)))()\rightarrow Rightarrow (S(\boldsymbol{S})((S)))()\rightarrowRightarrow(\boldsymbol{S}()((S)))()\rightarrowRightarrow(()((\boldsymbol{S})))()\rightarrowRightarrow(()(()))()</tex> {{Определение|definition='''Левосторонним выводом слова <tex>\alpha</tex>''' называется такой его вывод, что каждая последующая строка получена из предыдущей путем замены по одному из правил самого левого встречающегося в строке нетерминала.}}
{{Определение
|definition=
'''Левосторонним Правосторонним выводом слова <tex>\alpha</tex>''' называется такой его вывод, что каждая последующая строка получена из предыдущей путем замены по одному из правил самого левого правого встречающегося в строке нетерминала по одному из правил.
}}
Аналогичным образом определяется ''правосторонний вывод''.
<br>
Рассмотрим левосторонний вывод нашей скобочной последовательности:<br>
<tex>\boldsymbol{S}\rightarrow Rightarrow (\boldsymbol{S})S \rightarrow Rightarrow ((\boldsymbol{S})S)S\rightarrow Rightarrow (()\boldsymbol{S})S\rightarrowRightarrow(()\boldsymbol{S}(S))S\rightarrowRightarrow(()(\boldsymbol{S}))S\rightarrowRightarrow(()(\boldsymbol{S}(S)))S\rightarrowRightarrow(()((\boldsymbol{S})))S\rightarrowRightarrow(()(()))\boldsymbol{S}\rightarrowRightarrow(()(()))(\boldsymbol{S})S\rightarrowRightarrow(()(()))()\boldsymbol{S}\rightarrowRightarrow(()(()))()</tex>
{{Определение
|definition=
'''Деревом разбора грамматики''' (англ. ''parse tree'') называется дерево, в вершинах которого записаны терминалы или нетерминалы, а дети вершины, в которой записан нетерминал, соответствуют раскрытию нетерминала по одному любому правилу, в левой части которого стоит этот нетерминал, и упорядочены так же, как в правой части этого правила. Все вершины, помеченные терминалами, являются листьями. Все вершины, помеченные нетерминалами, имеют детей.
}}
{{Определение
|definition=
'''КронойКрона''' дерева разбора называется {{---}} множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева в глубину из корня.
}}
Крона дерева разбора представляет из себя слово языка, которое выводит это дерево.<br>
{{Определение
|definition=
Грамматика называется '''однозначной'''(англ. ''unambiguous grammar''), если у каждого слова имеется не более одного дерева разбора в этой грамматике.
}}
 
{{Лемма
|id=lemma-
|statement=
Пусть <tex>\Gamma</tex> {{---}} однозначная грамматика. Тогда <tex>\forall \omega \in \mathbb{L}(\Gamma)</tex> у существует ровно один левосторонний (правосторонний) вывод <tex>\omega</tex> существует ровно один левосторонний (правосторонний) вывод.
|proof=
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний вывод. Поскольку каждое слова из языка выводится только одним деревом разбора, то существует только один левосторонний вывод этого слова.
}}
 
== Литература ==
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.
137
правок

Навигация