Изменения
Опечатка в правилах вывода из S в шагах 4 и 5
{{Определение
|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'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержаться только правила одного из следующих типов:* :<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> {{---}} строка из произвольного числа терминалов и нетерминалов.
}}
== Приведение грамматики к ослабленной нормальной форме Грейбах ==
Рассмотрим контекстно-свободную грамматику <tex> \Gamma </tex>. Для приведения её к нормальной ослабленной форме Грейбах нужно выполнить три шага. На каждом шаге мы строим новую грамматику, допускающую тот же язык, что и <tex> \Gamma </tex>.
После каждой итерации главного цикла все правила для <tex> A_k </tex> (где <tex>k \ge geqslant i</tex>) будут иметь вид <tex> A_k \rightarrow a \gamma </tex>.
Значит, после применения процедуры все правила грамматики будут иметь вид <tex> A \rightarrow a \gamma </tex>.
Таким образом, мы получили грамматику в ослабленной нормальной форме Грейбах, которая допускает тот же язык, что и исходная.
}}
== Пример ==
{| border="1" class="wikitable" style="width: 500px; height: 500px; float: left;"
!style="background:#41aef0"|Текущий шаг
!style="background:#41aef0"|Грамматика после применения правила
|-
|''0. Исходная грамматика''
|<tex>S\rightarrow XA|BB</tex> <br> <tex>B\rightarrow b|SB</tex> <br> <tex>X\rightarrow b</tex><br> <tex>A\rightarrow a</tex>
|-
|''1. Удаление <tex>\varepsilon</tex>-правил''
|<tex>S\rightarrow XA|BB</tex> <br> <tex>B\rightarrow b|SB</tex> <br> <tex>X\rightarrow b</tex><br> <tex>A\rightarrow a</tex>
|-
|''2. Удаление стартового нетерминала из правых частей правил
|<tex>S\rightarrow XA|BB</tex> <br> <tex>B\rightarrow bAB|BBB|b</tex> <br> <tex>X\rightarrow b</tex><br> <tex>A\rightarrow a</tex>
|-
|''3. Удаление левой рекурсии
|<tex>S\rightarrow XA|BB</tex> <br> <tex>B\rightarrow bAB|b|bABZ|bZ</tex> <br> <tex>Z\rightarrow BB|BBZ</tex> <br> <tex>X\rightarrow b</tex> <br> <tex>A\rightarrow a</tex>
|-
|''4. Выполняем функцию '''greibah''' для правила <tex>S\rightarrow XA|BB</tex>
|<tex>S\rightarrow bA|bABB|bB|bABZB|bZB</tex> <br> <tex>B\rightarrow bAB|b|bABZ|bZ</tex> <br> <tex>Z\rightarrow BB|BBZ</tex> <br> <tex>X\rightarrow b</tex> <br> <tex>A\rightarrow a</tex>
|-
|''5. Выполняем функцию '''greibah''' для правила <tex>Z\rightarrow BB|BBZ</tex>
|<tex>S\rightarrow bA|bABB|bB|bABZB|bZB</tex> <br> <tex>B\rightarrow bAB|b|bABZ|bZ</tex> <br> <tex>Z\rightarrow bABB|bB|bABZB|bZB|bABBZ|bBZ|bABZBZ|bZBZ</tex> <br> <tex>X\rightarrow b</tex> <br> <tex>A\rightarrow a</tex>
|}
<div style="clear:both;"></div>
=== Асимптотика ===
Алгоритм состоит из трех шагов, сложность первого и последнего шага равны <tex>O(\left| \Gamma \right|)</tex> и <tex>O(\left| \Gamma \right| ^ 2)</tex> соответственно. Таким обзом, сложность алгоритма является <tex>O(\left| \Gamma \right| ^ 2) + O\left(n\sum\limits_{i=1}^n a_j\right)</tex>, где второй член {{---}} сложность алгоритма удаления левой рекурсии.
== Применение ==
'''Простота доказательств'''
Использование нормальных форм существенно упрощает доказательство теорем. Например, использование нормальной формы Грейбах позволяет доказать, что для каждого контекстно-свободного языка (не содержащего <tex>\varepsilon</tex>) существует автомат с магазинной памятью без переходов по <tex>\varepsilon</tex>. <ref>[http://www.cis.upenn.edu/~jean/old511/html/cis51108sl4b.pdf Jean Gallier {{---}} Discrete Mathematics]</ref>
'''Разбор грамматики'''
Нормальная форма Холмского позволяет производить разбор грамматики. Например, с помощью [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ|алгоритма Кока-Янгера-Касами]]. В свою очередь, нормальная форма Грейбах позволяет использовать метод рекурсивного спуска, сложность которого является линейной, несмотря на возвраты.
== См. также ==
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
* [[Нормальная_форма_Куроды | Нормальная форма Куроды]]
* [[Нормальная_форма_Хомского | Нормальная форма Хомского]]
==Примечания==
<references />
==Источники информации==
* [[wikipedia:en:Greibach normal form | Wikipedia {{---}} Greibach normal form]]
* [http://www.iitg.ernet.in/gkd/ma513/oct/oct18/note.pdf MA513: Formal Languages and Automata Theory]
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Нормальные формы КС-грамматик]]
