Изменения

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

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

270 байт убрано, 21:38, 21 декабря 2015
м
Источники информации
{{Определение
|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>-правил, могут образоваться новые цепные правила. Также четвертое правило должно быть выполнено позже третьегои второго, так как оно может они могут порождать бесполезные символы.
При таком порядке действий размеры грамматики возрастают полиномиально.
== Пример ==
{| border="1" class="wikitable" style="width: 450px500px; height: 450px500px; float: left;"!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>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_{23}S_{1}</tex><br> <tex>X\rightarrow S_{23}Y|X_{1}Y</tex><br> <tex>Y\rightarrow S_{23}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_{23}\rightarrow a</tex> <br> <tex>S_{34}\rightarrow y</tex> <br> <tex>X_{1}\rightarrow b</tex> <br> <tex>Y_{1}\rightarrow c</tex>
|}
<div style="clear:both;"></div>
== См. также ==
==Источники информации==
* [[wikipedia:en:Chomsky normal form | Wikipedia {{---}} Chomsky normal form]]
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 280с528с. : ISBN 5-8459-0261-4 (рус.)
275
правок

Навигация