317
правок
Изменения
Нет описания правки
Таким образом, мы получили грамматику в ослабленной нормальной форме Грейбах, которая допускает тот же язык, что и исходная.
}}
== Пример ==
{| border="1" class="wikitable" style="width: 500px; height: 500px; float: left;"
!style="background:#41aef0"|Текущий шаг
!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. Выполняем процедуру для правила <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. Выполняем процедуру для правила <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>
=== Асимптотика ===
==Источники информации==
* [[wikipedia:en:Greibach normal form | Wikipedia {{---}} Greibach normal form]]
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
