142
правки
Изменения
Нет описания правки
== Определение ==
{{Определение
|definition=Грамматикой в '''нормальной форме Грейбах''' (''Greibach normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержаться только правила одного из следующих типов:
* <tex> A \rightarrow a\gamma </tex>,
* <tex> S \rightarrow \varepsilon </tex>,
где <tex> a </tex> {{---}} терминал, <tex> A </tex> {{---}} нетерминал, <tex> S </tex> {{---}} стартовый нетерминал (причём он не должен встречаться в правых частях правил), <tex> \varepsilon </tex> {{---}} пустая строка, <tex> \gamma </tex> {{---}} строка из не более, чем двух нетерминалов.
}}
{{Определение
|definition=Грамматикой в '''ослабленной нормальной форме Грейбах''' (''Greibach weak normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержаться только правила одного из следующих типов:
