275
правок
Изменения
м
Рассмотрим пример для следующей грамматики:{| border="1" cellpadding="3" cellspacingclass="0wikitable" style="text-alignwidth:center500px; height: 500px; float: left;" width=60%!style="background:#f2f2f241aef0"|ПравилоТекущий шаг!style="background:#f2f2f241aef0"|Грамматика после применения правила
|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>S_{1}X\rightarrow XS_{2}aY|bY|\varepsilon</tex> <br> <tex>S_{2}Y\rightarrow yXX|cc</tex> <br> <tex>XZ\rightarrow aY|bY|\varepsilonZX</tex> <br> <tex>YS_{1}\rightarrow X|ccXS_{2}</tex> <br> <tex>ZS_{2}\rightarrow ZXyX</tex>
|style="background:#ffffff"|''2. Удаление <tex>\varepsilon</tex>-правил''|style="background:#ffffff"|<tex>S\rightarrow aS_{1}|aZ</tex> <br> <tex>S_{1}X\rightarrow XS_{2}aY|S_{2}bY</tex> <br> <tex>S_{2}Y\rightarrow yXaY|bY|ycc</tex> <br> <tex>XZ\rightarrow aY|bYZX</tex> <br> <tex>YS_{1}\rightarrow aYXS_{2}|bY|ccS_{2}</tex> <br> <tex>ZS_{2}\rightarrow ZXyX|y</tex>
|style="background:#ffffff"|''3. Удаление цепных правил''|style="background:#ffffff"|<tex>S\rightarrow aS_{1}|aZ</tex> <br> <tex>S_{1}X\rightarrow XS_{2}aY|yX|ybY</tex> <br> <tex>S_{2}Y\rightarrow yXaY|bY|ycc</tex> <br> <tex>XZ\rightarrow aY|bYZX</tex> <br> <tex>YS_{1}\rightarrow aYXS_{2}|bYyX|ccy</tex> <br> <tex>ZS_{2}\rightarrow ZXyX|y</tex>
|style="background:#ffffff"|''4. Удаление бесполезных символов''|style="background:#ffffff"|<tex>S\rightarrow aS_{1}</tex> <br> <tex>S_{1}X\rightarrow XS_{2}aY|yX|ybY</tex> <br> <tex>S_{2}Y\rightarrow yXaY|bY|ycc</tex> <br> <tex>XS_{1}\rightarrow aYXS_{2}|yX|bYy</tex> <br> <tex>YS_{2}\rightarrow aYyX|bY|ccy</tex>
|style="background:#ffffff"|''5. Уберём ситуации, когда в правиле встречаются несколько терминалов.''|style="background:#ffffff"|<tex>S\rightarrow S_{23}S_{1}</tex> <br> <tex>X\rightarrow S_{23}Y|X_{1}Y</tex> <br> <tex>Y\rightarrow aS_{3}Y|X_{1}Y|Y_{1}Y_{1}</tex> <br> <tex>S_{1}\rightarrow XS_{2}|S_{34}X|y</tex> <br> <tex>S_{2}\rightarrow S_{34}X|y</tex> <br> <tex>S_{3}\rightarrow ya</tex> <br> <tex>X\rightarrow S_{24}Y|X_{1}Y\rightarrow y</tex> <br> <tex>X_{1}\rightarrow b</tex> <br> <tex>Y\rightarrow S_{2}Y|X_{1}Y|Y_{1}Y_{1}</tex> <br> <tex>Y_{1}\rightarrow c</tex>
→Источники информации
{{Определение
|definition=Грамматикой в '''нормальной форме Хомского''' (англ. ''Chomsky normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержаться правила только следующего вида:
:<tex>A \rightarrow B C </tex>,
:<tex>A \rightarrow a </tex>,
:<tex>S \rightarrow \varepsilon </tex>,
где <tex> a </tex> {{---}} терминал, <tex> A, B, C </tex> {{---}} нетерминалы, <tex> S </tex> {{---}} стартовая вершина, <tex> \varepsilon </tex> {{---}} пустая строка, стартовая вершина не содержится в правых частях правил.
Таким образом, мы получили грамматику в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma </tex>.
Стоит заметить, что порядок выполнения операций важен. Первое правило должно быть выполнено перед вторым, иначе время нормализации ухудшится до <tex>O(2^{\left| \Gamma \right|})</tex>. Третье правило идет после второго, потому что после удаления <tex>\varepsilon</tex>-правил, могут образоваться новые цепные правила. Также четвертое правило должно быть выполнено после позже третьегои второго, так как оно может они могут порождать бесполезные символы.
При таком порядке действий размеры грамматики возрастают полиномиально.
== Пример ==
|-
|-
|-
|-
|-
|-
|}
<div style="clear:both;"></div>
== См. также ==
==Источники информации==
* [[wikipedia:en:Chomsky normal form | Wikipedia {{---}} Chomsky normal form]]
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 280с528с. : ISBN 5-8459-0261-4 (рус.)
