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

Визначення:
Граматикою внормальній формі Грейбах(англ.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. Скористаємося алгоритмом усунення лівої рекурсії. Отримаємо граматику, всі правила якої будуть мати такий вигляд:
  3. [math] A_i \rightarrow a \gamma [/math] ,
  4. [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].
  5. Скористаємося наступною функцією для надання граматиці потрібного вигляду:

Після кожної ітерації головного циклу всі правила для [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 XABB[/math] [math]B\rightarrow bSB[/math] [math]X\rightarrow b[/math] [math]A\rightarrow a[ /math]
1. Вилучення [math]\varepsilon[/math]-правил[math]S\rightarrow XABB[/math] [math]B\rightarrow bSB[/math] [math]X\rightarrow b[/math] [math]A\rightarrow a[ /math]
2. Видалення стартового нетерміналу із правих частин правил[math]S\rightarrow XABB[/math] [math]B\rightarrow bABBBBb[/math] [math]X\rightarrow b[/math] [math]A\rightarrow a[ /math]
3. Видалення лівої рекурсії[math]S\rightarrow XABB[/math] [math]B\rightarrow bABbbABZbZ[/math] [math]Z\rightarrow BBBBZ[/math] [math]X\rightarrow b[ /math] [math]A\rightarrow a[/math]
4. Виконуємо функціюgreibahдля правила [math]S\rightarrow XABB[/math][math]S\rightarrow bAbABBbBbABZBbZB[/math] [math]B\rightarrow bABbbABZbZ[/math] [math]Z\rightarrow BBBBZ[/math] [math]X\rightarrow b[ /math] [math]A\rightarrow a[/math]
5. Виконуємо функціюgreibahдля правила [math]Z\rightarrow BBBBZ[/math][math]S\rightarrow bAbABBbBbABBZBbZB[/math] [math]B\rightarrow bABbbABZbZ[/math] [math]Z\rightarrow bABBbBBABZBbZBbABBZbBZbABZBZbZBZ /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_^n a_j\right)[/math] , де другий член - складність алгоритму видалення лівої рекурсії .

Застосування [ред.]

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

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