Изменения

Перейти к: навигация, поиск

Нормальная форма Хомского

324 байта убрано, 13:05, 20 декабря 2015
Пример
== Пример ==
{| border="1" class="wikitable" style="width: 600px900px; height: 600px900px; float: left;"
!style="background:#f2f2f2"|Текущий шаг
!style="background:#f2f2f2"|Грамматика после применения правила
|-
|style="background:#ffffff"|''0. Исходная грамматика''|style="background:#ffffff"|<tex>S\rightarrow aXbX|aZ</tex> <br> <tex>X\rightarrow aY|bY|\varepsilon</tex> <br> <tex>Y\rightarrow X|cc</tex><br> <tex>Z\rightarrow ZX</tex>
|-
|style="background:#ffffff"|''1. Удаление длинных правил''|style="background:#ffffff"|<tex>S\rightarrow aS_{1}|aZ</tex> <br> <tex>X\rightarrow aY|bY|\varepsilon</tex> <br> <tex>Y\rightarrow X|cc</tex> <br> <tex>Z\rightarrow ZX</tex> <br> <tex>S_{1}\rightarrow XS_{2}</tex> <br> <tex>S_{2}\rightarrow yX</tex>
|-
|style="background:#ffffff"|''2. Удаление <tex>\varepsilon</tex>-правил''|style="background:#ffffff"|<tex>S\rightarrow aS_{1}|aZ</tex><br> <tex>X\rightarrow aY|bY</tex> <br> <tex>Y\rightarrow aY|bY|cc</tex> <br> <tex>Z\rightarrow ZX</tex> <br> <tex>S_{1}\rightarrow XS_{2}|S_{2}</tex> <br> <tex>S_{2}\rightarrow yX|y</tex>
|-
|style="background:#ffffff"|''3. Удаление цепных правил''|style="background:#ffffff"|<tex>S\rightarrow aS_{1}|aZ</tex><br> <tex>X\rightarrow aY|bY</tex> <br> <tex>Y\rightarrow aY|bY|cc</tex> <br> <tex>Z\rightarrow ZX</tex> <br> <tex>S_{1}\rightarrow XS_{2}|yX|y</tex> <br> <tex>S_{2}\rightarrow yX|y</tex>
|-
|style="background:#ffffff"|''4. Удаление бесполезных символов''|style="background:#ffffff"|<tex>S\rightarrow aS_{1}</tex> <br> <tex>X\rightarrow aY|bY</tex> <br> <tex>Y\rightarrow aY|bY|cc</tex> <br> <tex>S_{1}\rightarrow XS_{2}|yX|y</tex> <br> <tex>S_{2}\rightarrow yX|y</tex>
|-
|style="background:#ffffff"|''5. Уберём ситуации, когда в правиле встречаются несколько терминалов.''|style="background:#ffffff"|<tex>S\rightarrow S_{2}S_{1}</tex><br> <tex>X\rightarrow S_{2}Y|X_{1}Y</tex><br> <tex>Y\rightarrow S_{2}Y|X_{1}Y|Y_{1}Y_{1}</tex> <br> <tex>S_{1}\rightarrow XS_{2}|S_{3}X|y</tex> <br> <tex>S_{2}\rightarrow S_{3}X|y</tex> <br> <tex>S_{2}\rightarrow a</tex> <br> <tex>S_{3}\rightarrow y</tex> <br> <tex>X_{1}\rightarrow b</tex> <br> <tex>Y_{1}\rightarrow c</tex>
|}
275
правок

Навигация