Изменения

|definition=Грамматикой в '''нормальной форме Грейбах ''' (англ. ''Greibach normal form'') называется к.с. [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой содержатся могут содержаться только правила видаодного из следующих типов::<tex>A \rightarrow a B C \gamma </tex>

:<tex>A S \rightarrow \varepsilon </tex>где <tex> a B</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> {{---}} нетерминал (возможно, Bстартовый), C<tex> S </tex> {{-- нетерминалы-}} стартовый нетерминал (причём он не должен встречаться в правых частях правил)и, быть может, правило <tex>S \rightarrow \epsilonvarepsilon </tex> (где {{---}} пустая строка, <tex>S\gamma </tex> {{--- начальный символ)}} строка из произвольного числа терминалов и нетерминалов.

(== Приведение грамматики к ослабленной нормальной форме Грейбах =={{Теорема|statement=Любую контекстно-свободную грамматику можно привести к ослабленной нормальной форме Грейбах.|proof=Рассмотрим контекстно-свободную грамматику <tex> \Gamma </tex>. Для приведения её к нормальной ослабленной форме Грейбах нужно выполнить три шага. На каждом шаге мы строим новую грамматику, допускающую тот же язык, что и <tex> \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>\alphagamma </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>S A_i \rightarrow A_j \gamma </tex> на <tex> A_i \rightarrow \epsilondelta_1\gamma | \ldots | \delta_k\gamma </tex>. После каждой итерации главного цикла все правила для <tex> A_k </tex> (в этом случае где <tex>k \geqslant i</tex>) будут иметь вид <tex> A_k \rightarrow a \gamma </tex>S.Значит, после применения процедуры все правила грамматики будут иметь вид <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\Gammarightarrow XA|BB</tex> <br> <tex>B\rightarrow b|SB</tex> <br> <tex>X\rightarrow b</tex><br> <tex>A\rightarrow a</tex> можно привести к требуемой форме следующим образом:#Воспользоваться [[Удаление_eps|-|''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>| алгоритмом удаления &epsilon;-|''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. Получим грамматику без &epsilon;Удаление левой рекурсии|<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>L(S\Gamma) rightarrow bA|bABB|bB|bABZB|bZB</tex> <br> <tex>B\setminus rightarrow bAB|b|bABZ|bZ</tex> <br> <tex>Z\lbrace rightarrow BB|BBZ</tex> <br> <tex>X\epsilon rightarrow b</tex> <br> <tex>A\rbracerightarrow 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\epsilonrightarrow a</tex> присутствовал в языке исходной грамматики|}<div style="clear:both;"></div>  === Асимптотика === Алгоритм состоит из трех шагов, добавить новый начальный символ сложность первого и последнего шага равны <tex>S'O(\left| \Gamma \right|)</tex> и правила <tex>S' O(\left| \rightarrow S Gamma \right| ^ 2)</tex> соответственно. Таким обзом, сложность алгоритма является <tex>O(\left| \Gamma \right| ^ 2) + O\left(n\sum\limits_{i=1}^n a_j\right)</tex>, где второй член {{---}} сложность алгоритма удаления левой рекурсии. == Применение =='''Простота доказательств''' Использование нормальных форм существенно упрощает доказательство теорем. Например, использование нормальной формы Грейбах позволяет доказать, что для каждого контекстно-свободного языка (не содержащего <tex>\epsilon varepsilon</tex>) существует автомат с магазинной памятью без переходов по <tex>\varepsilon</tex>. <ref>[http://www.cis.upenn.edu/~jean/old511/html/cis51108sl4b.pdf Jean Gallier {{---}} Discrete Mathematics]</ref> '''Разбор грамматики''' Нормальная форма Холмского позволяет производить разбор грамматики. Например, с помощью [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ|алгоритма Кока-Янгера-Касами]]. В свою очередь, нормальная форма Грейбах позволяет использовать метод рекурсивного спуска, сложность которого является линейной, несмотря на возвраты. == См. также ==* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]* [[Нормальная_форма_Куроды | Нормальная форма Куроды]]* [[Нормальная_форма_Хомского | Нормальная форма Хомского]] ==Примечания==

===Алгоритм для грамматики без ε-правил===Первым делом, используем [[Устранение_левой_рекурсии|алгоритм устранения левой рекурсии]]. После этого все правила грамматики будут иметь вид*<tex>A_i \rightarrow a \alpha </tex>, где <tex>\alpha</tex> - терминал*<tex>A_i \rightarrow A_j \alpha </tex>, где <tex>i < j<references /tex>

Затем проведем процедуру, похожую на используемую при устранении левой рекурсии:: for i = n downto 1 {=Источники информации==* [[wikipedia:en:for j = n downto i + 1 Greibach normal form | Wikipedia {{---}} Greibach normal form]]* [http:::* рассмотреть все правила вывода из <math>A_j</math>:::<math>A_j \rightarrow \delta_1 | \ldots | \delta_k</math>:::* заменить каждое правило <math>A_i \rightarrow A_j \gamma<www.iitg.ernet.in/math> на:::<math>A_i \rightarrow \delta_1\gamma | \ldots | \delta_k\gamma<gkd/math>::}:}Легко видеть, что после итерации главного цикла для значения <tex>i<ma513/tex> все правила для <tex>A_k, \, k \ge i<oct/tex> будут иметь вид <tex>A_k \rightarrow a \alpha<oct18/tex>note.pdf MA513: Formal Languages and Automata Theory]

Следовательно, после применения процедуры все правила [[Категория: Теория формальных языков]][[Категория: Контекстно-свободные грамматики будут иметь вид <tex>A \rightarrow a \alpha</tex>.]][[Категория: Нормальные формы КС-грамматик]]