Бюрократы, editor, Администраторы
422
правки
Изменения
Нет описания правки
== Определение ==
{{Определение
|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> {{---}} строка из произвольного количества числа терминалов и нетерминалов, стартовая вершина не содержится в правых частях правил.
}}
|statement=Любую контекстно-свободную грамматику можно привести к ослабленной нормальной форме Грейбах.
|proof=
Рассмотрим контекстно-свободную грамматику <tex> \Gamma </tex>. Для приведения ее её к нормальной ослабленной форме Грейбах нужно выполнить три шага. На каждом шаге мы строим новую <tex> \Gamma_i </tex>грамматику, которая допускает допускающую тот же язык, что и <tex> \Gamma </tex>.
<ol>
<li> Избавимся от <tex> \varepsilon </tex>-правил.
Для этого воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]]. Получим грамматику <tex> \Gamma_1 </tex>.
</li>
<li> Воспользуемся [[Устранение_левой_рекурсии|алгоритмом устранения левой рекурсии]].
Получим грамматику <tex> \Gamma_2 </tex>, все правила которой будут иметь следующий вид:
<ul>
<li> <tex> A_i \rightarrow a \gamma </tex>, </li>
Для каждого правила вывода из <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>.
</div>
После каждой итерации главного цикла все правила для <tex> A_k, \, k \ge i </tex> будут иметь вид <tex> A_k \rightarrow a \alpha </tex>.
</ol>
Таким образом мы получили грамматику <tex> \Gamma_3 </tex> в ослабленной нормальной форме Грейбах, которая допускает то же язык, что и <tex> \Gamma </tex>.
}}
