Изменения

'''Контекстно-свободной грамматикой''' (англ. ''сontext-free grammar'') называется грамматика, у которой в левых частях всех правил стоят только одиночные нетерминалы. <br>Язык, задаваемый контекстно}}{{Определение|definition='''Контекстно-свободной грамматикой называется свободный язык'''(англ. ''контекстноcontext-свободным языком'free language'') {{---}} язык, задаваемый контекстно-свободной грамматикой.

'''Выводом слова''' <tex>\alpha</tex> называется последовательность строк, состоящих из терминалов и нетерминалов, где первой идет . Первая строка, состоящая последовательности состоит из одного стартового нетерминала, а каждая . Каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, и а последней строкой в последовательности является слово <tex>\alpha</tex>.

Рассмотрим на примере грамматики, выводящей все правильные скобочные последовательности.  Терминальные символы {{---}} <tex>"(" </tex> и <tex>")", нетерминал </tex>;  <tex>S</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>''' называется такой его вывод, что каждая последующая строка получена из предыдущей путем замены по одному из правил самого левого встречающегося в строке нетерминала.}}

'''Левосторонним Правосторонним выводом слова <tex>\alpha</tex>''' называется такой его вывод, что каждая последующая строка получена из предыдущей путем замены по одному из правил самого левого правого встречающегося в строке нетерминала по одному из правил.

<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>

'''Деревом разбора грамматики''' (англ. ''parse tree'') называется дерево, в вершинах которого записаны терминалы или нетерминалы, а дети вершины, в которой записан нетерминал, соответствуют раскрытию нетерминала по одному любому правилу, в левой части которого стоит этот нетерминал, и упорядочены так же, как в правой части этого правила. Все вершины, помеченные терминалами, являются листьями. Все вершины, помеченные нетерминалами, имеют детей.

'''КронойКрона''' дерева разбора называется {{---}} множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева в глубину из корня.

Грамматика называется '''однозначной'''(англ. ''unambiguous grammar''), если у каждого слова имеется не более одного дерева разбора в этой грамматике.

Пусть <tex>\Gamma</tex> {{---}} однозначная грамматика. Тогда <tex>\forall \omega \in \mathbb{L}(\Gamma)</tex> у существует ровно один левосторонний (правосторонний) вывод <tex>\omega</tex> существует ровно один левосторонний (правосторонний) вывод.