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

Определение:

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

Определение:

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

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

Теорема:

Любую контекстно-свободную грамматику можно привести к ослабленной нормальной форме Грейбах.

Доказательство:

$\triangleright$

Рассмотрим контекстно-свободную грамматику $\Gamma$. Для приведения её к нормальной ослабленной форме Грейбах нужно выполнить три шага. На каждом шаге мы строим новую грамматику, допускающую тот же язык, что и $\Gamma$. Избавимся от $\varepsilon$-правил. Для этого воспользуемся алгоритмом удаления $\varepsilon$-правил. Воспользуемся алгоритмом устранения левой рекурсии.Получим грамматику, все правила которой будут иметь следующий вид: $A_i \rightarrow a \gamma$, $A_i \rightarrow A_j \gamma$, где $A_i$, $A_j$ — нетерминалы, $a$ — терминал, $\gamma$ — произвольная последовательность из терминалов и нетерминалов, $i \lt j$. Воспользуемся следующей функцией для придания грамматике нужного вида: function greibah(правила $A_1 \dots A_n$ из контекстно-свободной грамматики $\Gamma$): for i = n .. 1 for j = i + 1 .. n Для каждого правила вывода из $A_j$ вида $A_j \rightarrow \delta_1 | \ldots | \delta_k$ заменить каждое правило $A_i \rightarrow A_j \gamma$ на $A_i \rightarrow \delta_1\gamma | \ldots | \delta_k\gamma$. После каждой итерации главного цикла все правила для $A_k$ (где $k \geqslant i$) будут иметь вид $A_k \rightarrow a \gamma$. Значит, после применения процедуры все правила грамматики будут иметь вид $A \rightarrow a \gamma$. Таким образом, мы получили грамматику в ослабленной нормальной форме Грейбах, которая допускает тот же язык, что и исходная.

$\triangleleft$

Пример

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

Асимптотика

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

Применение

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

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

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

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

См. также

• Контекстно-свободные грамматики
• Нормальная форма Куроды
• Нормальная форма Хомского

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

• Wikipedia — Greibach normal form
• MA513: Formal Languages and Automata Theory