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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=Грамматикой в '''нормальной форме Грейбах''' (англ. ''Greibach normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержаться только правила одного из следующих типов:
 
|definition=Грамматикой в '''нормальной форме Грейбах''' (англ. ''Greibach normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержаться только правила одного из следующих типов:
* <tex> A \rightarrow a\gamma </tex>,
+
<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> S \rightarrow \varepsilon </tex>
 +
где <tex> a </tex> {{---}} терминал, <tex> A </tex> {{---}} нетерминал, <tex> S </tex> {{---}} стартовый нетерминал (причём он не должен встречаться в правых частях правил), <tex> \varepsilon </tex> {{---}} пустая строка, <tex> \gamma </tex> {{---}} строка из не более, чем двух нетерминалов. Таким образом, пустая строка выводится только из стартового нетерминала. Однако он по-прежнему может участвовать в формировании правил первого типа. (Это утверждение применимо и к ослабленной нормальной форме Грейбах)
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=Грамматикой в '''ослабленной нормальной форме Грейбах''' (англ. ''Greibach weak normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержаться только правила одного из следующих типов:
 
|definition=Грамматикой в '''ослабленной нормальной форме Грейбах''' (англ. ''Greibach weak normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержаться только правила одного из следующих типов:
* <tex> A \rightarrow a\gamma </tex>,
+
<tex> A \rightarrow a\gamma </tex>
* <tex> S \rightarrow \varepsilon </tex>,
+
 
 +
<tex> S \rightarrow \varepsilon </tex>
 
где <tex> a </tex> {{---}} терминал, <tex> A </tex> {{---}} нетерминал, <tex> S </tex> {{---}} стартовый нетерминал (причём он не должен встречаться в правых частях правил), <tex> \varepsilon </tex> {{---}} пустая строка, <tex> \gamma </tex> {{---}} строка из произвольного числа терминалов и нетерминалов.   
 
где <tex> a </tex> {{---}} терминал, <tex> A </tex> {{---}} нетерминал, <tex> S </tex> {{---}} стартовый нетерминал (причём он не должен встречаться в правых частях правил), <tex> \varepsilon </tex> {{---}} пустая строка, <tex> \gamma </tex> {{---}} строка из произвольного числа терминалов и нетерминалов.   
 
}}
 
}}
 +
  
 
== Приведение грамматики к ослабленной нормальной форме Грейбах ==
 
== Приведение грамматики к ослабленной нормальной форме Грейбах ==

Версия 23:55, 6 декабря 2016

Определение:
Грамматикой в нормальной форме Грейбах (англ. 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. Воспользуемся следующей процедурой для придания грамматике нужного вида:
for i = n .. 1
   for j = i + 1 .. n
      Для каждого правила вывода из [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 \ge 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. Выполняем процедуру для правила [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. Выполняем процедуру для правила [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].

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

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

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