| Определение: |
Грамматикой в нормальной форме Грейбах (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].
- Избавимся от [math] \varepsilon [/math]-правил.
Для этого воспользуемся алгоритмом удаления [math] \varepsilon [/math]-правил.
- Воспользуемся алгоритмом устранения левой рекурсии.
Получим грамматику, все правила которой будут иметь следующий вид:
- [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].
-
Воспользуемся следующей процедурой для придания грамматике нужного вида:
for i = n downto 1
for j = i + 1 to 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] |
Асимптотика
Алгоритм состоит из трех шагов, сложность первого и последнего шага равны [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].
Разбор грамматики
Нормальная форма Холмского позволяет производить разбор грамматики. Например, с помощью алгоритма Кока-Янгера-Касами. В свою очередь, нормальная форма Грейбах позволяет использовать метод рекурсивного спуска, сложность которого является линейной, несмотря на возвраты.
