Приведение грамматики к ослабленной нормальной форме Грейбах — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(Опечатка в правилах вывода из S в шагах 4 и 5)
(не показано 47 промежуточных версий 10 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition=Грамматикой в нормальной форме Грейбах (Greibach normal form) называется к.с. грамматика, в которой содержатся только правила вида
+
|definition=Грамматикой в '''нормальной форме Грейбах''' (англ. ''Greibach normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержаться только правила одного из следующих типов:
<tex>A \rightarrow a B C </tex>  
+
:<tex> A \rightarrow a\gamma </tex>
  
<tex>A \rightarrow a B</tex>
+
:<tex> S \rightarrow \varepsilon </tex>
 +
где <tex> a </tex> {{---}} терминал, <tex> A </tex> {{---}} нетерминал (возможно, стартовый), <tex> S </tex> {{---}} стартовый нетерминал (причём он не должен встречаться в правых частях правил), <tex> \varepsilon </tex> {{---}} пустая строка, <tex> \gamma </tex> {{---}} строка из не более, чем двух нетерминалов.
 +
}}
  
<tex>A \rightarrow a</tex>
+
{{Определение
 +
|definition=Грамматикой в '''ослабленной нормальной форме Грейбах''' (англ. ''Greibach weak normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержаться только правила одного из следующих типов:
 +
:<tex> A \rightarrow a\gamma </tex>
  
(где <tex>a</tex> - терминал, <tex>A, B, C</tex> - нетерминалы)
+
:<tex> S \rightarrow \varepsilon </tex>
и, быть может, правило <tex>S \rightarrow \epsilon</tex> (где <tex>S</tex> - начальный символ)
+
где <tex> a </tex> {{---}} терминал, <tex> A </tex> {{---}} нетерминал (возможно, стартовый), <tex> S </tex> {{---}} стартовый нетерминал (причём он не должен встречаться в правых частях правил), <tex> \varepsilon </tex> {{---}} пустая строка, <tex> \gamma </tex> {{---}} строка из произвольного числа терминалов и нетерминалов. 
 
}}
 
}}
{{Определение
 
|definition=Грамматикой в ослабленной нормальной форме Грейбах называется к.с. грамматика, в которой содержатся только правила вида
 
<tex>A \rightarrow a \alpha</tex>
 
  
(где <tex>a</tex> - терминал, <tex>\alpha</tex> - строка из терминалов и нетерминалов)
+
 
и, быть может, правило <tex>S \rightarrow \epsilon</tex> (в этом случае <tex>S</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> \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>.
 +
 
 +
Таким образом, мы получили грамматику в ослабленной нормальной форме Грейбах, которая допускает тот же язык, что и исходная.
 
}}
 
}}
==Алгоритм приведения грамматики к ослабленной нормальной форме Грейбах==
 
Приведем алгоритм, позволяющий для к.с. грамматики '''без &epsilon;-правил''' построить эквивалентную ей к.с. грамматику (без &epsilon;-правил), содержащую только правила вида <tex>A \rightarrow a \alpha</tex>.
 
  
Произвольную грамматику <tex>\Gamma</tex> можно привести к требуемой форме следующим образом:
+
== Пример ==
#Воспользоваться [[Удаление_eps-правил_из_грамматики | алгоритмом удаления &epsilon;-правил]]. Получим грамматику без &epsilon;-правил для языка <tex>L(\Gamma) \setminus \lbrace \epsilon \rbrace</tex>
+
{| border="1" class="wikitable" style="width: 500px; height: 500px; float: left;"
#Воспользоваться алгоритмом для новой грамматики
+
!style="background:#41aef0"|Текущий шаг
#Если <tex>\epsilon</tex> присутствовал в языке исходной грамматики, добавить новый начальный символ <tex>S'</tex> и правила <tex>S' \rightarrow S \, | \, \epsilon </tex>
+
!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 />
Первым делом, используем [[Устранение_левой_рекурсии|алгоритм устранения левой рекурсии]]. После этого все правила грамматики будут иметь вид
 
*<tex>A_i \rightarrow a \alpha </tex>, где <tex>\alpha</tex> - терминал
 
*<tex>A_i \rightarrow A_j \alpha </tex>, где <tex>i < j</tex>
 
  
Затем проведем процедуру, похожую на используемую при устранении левой рекурсии:
+
==Источники информации==
: for i = n downto 1 {
+
* [[wikipedia:en:Greibach normal form | Wikipedia {{---}} Greibach normal form]]
::for j = n downto i + 1 {
+
* [http://www.iitg.ernet.in/gkd/ma513/oct/oct18/note.pdf MA513: Formal Languages and Automata Theory]
:::* рассмотреть все правила вывода из <math>A_j</math>
 
:::<math>A_j \rightarrow \delta_1 | \ldots | \delta_k</math>
 
:::* заменить каждое правило <math>A_i \rightarrow A_j \gamma</math> на
 
:::<math>A_i \rightarrow \delta_1\gamma | \ldots | \delta_k\gamma</math>
 
::}
 
:}
 
Легко видеть, что после итерации главного цикла для значения <tex>i</tex> все правила для <tex>A_k, \, k \ge i</tex> будут иметь вид <tex>A_k \rightarrow a \alpha</tex>.
 
  
Следовательно, после применения процедуры все правила грамматики будут иметь вид <tex>A \rightarrow a \alpha</tex>.
+
[[Категория: Теория формальных языков]]
 +
[[Категория: Контекстно-свободные грамматики]]
 +
[[Категория: Нормальные формы КС-грамматик]]

Версия 22:55, 26 февраля 2019

Определение:
Грамматикой в нормальной форме Грейбах (англ. Greibach normal form) называется контекстно-свободная грамматика, в которой могут содержаться только правила одного из следующих типов:
[math] A \rightarrow a\gamma [/math]
[math] S \rightarrow \varepsilon [/math]
где [math] a [/math] — терминал, [math] A [/math] — нетерминал (возможно, стартовый), [math] S [/math] — стартовый нетерминал (причём он не должен встречаться в правых частях правил), [math] \varepsilon [/math] — пустая строка, [math] \gamma [/math] — строка из не более, чем двух нетерминалов.


Определение:
Грамматикой в ослабленной нормальной форме Грейбах (англ. Greibach weak normal form) называется контекстно-свободная грамматика, в которой могут содержаться только правила одного из следующих типов:
[math] A \rightarrow a\gamma [/math]
[math] S \rightarrow \varepsilon [/math]
где [math] a [/math] — терминал, [math] A [/math] — нетерминал (возможно, стартовый), [math] S [/math] — стартовый нетерминал (причём он не должен встречаться в правых частях правил), [math] \varepsilon [/math] — пустая строка, [math] \gamma [/math] — строка из произвольного числа терминалов и нетерминалов.


Приведение грамматики к ослабленной нормальной форме Грейбах

Теорема:
Любую контекстно-свободную грамматику можно привести к ослабленной нормальной форме Грейбах.
Доказательство:
[math]\triangleright[/math]

Рассмотрим контекстно-свободную грамматику [math] \Gamma [/math]. Для приведения её к нормальной ослабленной форме Грейбах нужно выполнить три шага. На каждом шаге мы строим новую грамматику, допускающую тот же язык, что и [math] \Gamma [/math].

  1. Избавимся от [math] \varepsilon [/math]-правил. Для этого воспользуемся алгоритмом удаления [math] \varepsilon [/math]-правил.
  2. Воспользуемся алгоритмом устранения левой рекурсии.Получим грамматику, все правила которой будут иметь следующий вид:
    • [math] A_i \rightarrow a \gamma [/math],
    • [math] A_i \rightarrow A_j \gamma [/math], где [math] A_i [/math], [math] A_j [/math] — нетерминалы, [math] a [/math] — терминал, [math] \gamma [/math] — произвольная последовательность из терминалов и нетерминалов, [math] i \lt j [/math].
  3. Воспользуемся следующей функцией для придания грамматике нужного вида:
function greibah(правила [math]A_1 \dots A_n[/math] из контекстно-свободной грамматики [math] \Gamma [/math]): 
   for i = n .. 1
      for j = i + 1 .. n
         Для каждого правила вывода из [math] A_j [/math] вида [math] A_j \rightarrow \delta_1 | \ldots | \delta_k [/math] заменить каждое правило [math] A_i \rightarrow A_j \gamma [/math] на [math] A_i \rightarrow \delta_1\gamma | \ldots | \delta_k\gamma [/math].

После каждой итерации главного цикла все правила для [math] A_k [/math] (где [math]k \geqslant i[/math]) будут иметь вид [math] A_k \rightarrow a \gamma [/math]. Значит, после применения процедуры все правила грамматики будут иметь вид [math] A \rightarrow a \gamma [/math].

Таким образом, мы получили грамматику в ослабленной нормальной форме Грейбах, которая допускает тот же язык, что и исходная.
[math]\triangleleft[/math]

Пример

Текущий шаг Грамматика после применения правила
0. Исходная грамматика [math]S\rightarrow XA|BB[/math]
[math]B\rightarrow b|SB[/math]
[math]X\rightarrow b[/math]
[math]A\rightarrow a[/math]
1. Удаление [math]\varepsilon[/math]-правил [math]S\rightarrow XA|BB[/math]
[math]B\rightarrow b|SB[/math]
[math]X\rightarrow b[/math]
[math]A\rightarrow a[/math]
2. Удаление стартового нетерминала из правых частей правил [math]S\rightarrow XA|BB[/math]
[math]B\rightarrow bAB|BBB|b[/math]
[math]X\rightarrow b[/math]
[math]A\rightarrow a[/math]
3. Удаление левой рекурсии [math]S\rightarrow XA|BB[/math]
[math]B\rightarrow bAB|b|bABZ|bZ[/math]
[math]Z\rightarrow BB|BBZ[/math]
[math]X\rightarrow b[/math]
[math]A\rightarrow a[/math]
4. Выполняем функцию greibah для правила [math]S\rightarrow XA|BB[/math] [math]S\rightarrow bA|bABB|bB|bABZB|bZB[/math]
[math]B\rightarrow bAB|b|bABZ|bZ[/math]
[math]Z\rightarrow BB|BBZ[/math]
[math]X\rightarrow b[/math]
[math]A\rightarrow a[/math]
5. Выполняем функцию greibah для правила [math]Z\rightarrow BB|BBZ[/math] [math]S\rightarrow bA|bABB|bB|bABZB|bZB[/math]
[math]B\rightarrow bAB|b|bABZ|bZ[/math]
[math]Z\rightarrow bABB|bB|bABZB|bZB|bABBZ|bBZ|bABZBZ|bZBZ[/math]
[math]X\rightarrow b[/math]
[math]A\rightarrow a[/math]


Асимптотика

Алгоритм состоит из трех шагов, сложность первого и последнего шага равны [math]O(\left| \Gamma \right|)[/math] и [math]O(\left| \Gamma \right| ^ 2)[/math] соответственно. Таким обзом, сложность алгоритма является [math]O(\left| \Gamma \right| ^ 2) + O\left(n\sum\limits_{i=1}^n a_j\right)[/math], где второй член — сложность алгоритма удаления левой рекурсии.

Применение

Простота доказательств

Использование нормальных форм существенно упрощает доказательство теорем. Например, использование нормальной формы Грейбах позволяет доказать, что для каждого контекстно-свободного языка (не содержащего [math]\varepsilon[/math]) существует автомат с магазинной памятью без переходов по [math]\varepsilon[/math]. [1]

Разбор грамматики

Нормальная форма Холмского позволяет производить разбор грамматики. Например, с помощью алгоритма Кока-Янгера-Касами. В свою очередь, нормальная форма Грейбах позволяет использовать метод рекурсивного спуска, сложность которого является линейной, несмотря на возвраты.

См. также

Примечания

Источники информации