Изменения
Опечатка в правилах вывода из S в шагах 4 и 5
{{Определение
|definition=Грамматикой в '''ослабленной нормальной форме Грейбах''' (англ. ''Greibach weaked 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> {{---}} строка из произвольного количества числа терминалов и нетерминалов, стартовая вершина не содержится в правых частях правил.
}}
== Приведение грамматики к ослабленной нормальной форме Грейбах ==
|statement=Любую контекстно-свободную грамматику можно привести к ослабленной нормальной форме Грейбах.
|proof=
Рассмотрим контекстно-свободную грамматику <tex> \Gamma </tex>. Для приведения ее её к нормальной ослабленной форме Грейбах нужно выполнить три шага. На каждом шаге мы строим новую грамматику, допускающую тот же язык, что и <tex> \Gamma_i Gamma </tex>. #Избавимся от <tex> \varepsilon </tex>-правил. Для этого воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]].#Воспользуемся [[Устранение_левой_рекурсии|алгоритмом устранения левой рекурсии]].Получим грамматику, все правила которой будут иметь следующий вид:#* <tex> A_i \rightarrow a \gamma </tex>, #* <tex> A_i \rightarrow A_j \gamma </tex>, где <tex> A_i </tex>, <tex> A_j </tex> {{---}} нетерминалы, <tex> a </tex> {{---}} терминал, <tex> \gamma </tex> {{---}} произвольная последовательность из терминалов и нетерминалов, <tex> i < j </tex>.#Воспользуемся следующей функцией для придания грамматике нужного вида: '''function''' greibah(правила <tex>A_1 \dots A_n</tex> из контекстно-свободной грамматики <tex> \Gamma </tex>): '''for''' i = n .. 1 '''for''' j = i + 1 .. n Для каждого правила вывода из <tex> A_j </tex> вида <tex> A_j \rightarrow \delta_1 | \ldots | \delta_k </tex> заменить каждое правило <tex> A_i \rightarrow A_j \gamma </tex> на <tex> A_i \rightarrow \delta_1\gamma | \ldots | \delta_k\gamma </tex>. После каждой итерации главного цикла все правила для <tex> A_k </tex> (где <tex>k \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\Gamma 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>