Изменения

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

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

1009 байт добавлено, 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: 500px; height: 500px; float: left;"!style="background: #41aef0"|Текущий шаг!style="background:#41aef0"|Грамматика после применения правила|-|''0. Исходная грамматика''|<tex>S\rightarrow aXbX|aZ</tex> <br> <tex>X\rightarrow aY|bY|\varepsilon</tex> <br> <tex>Y\rightarrow X|(S)|SScc</tex><br> <tex>Z\rightarrow ZX</tex>|-|''1.Удаление длинных правил''# Удалим длинные правила и получим грамматику |<tex>S\beginrightarrow aS_{array1}{l l} S|aZ</tex> <br> <tex>X\rightarrow \varepsilonaY|A)bY|SS\varepsilon</tex> <br> <tex>Y\ Arightarrow X|cc</tex> <br> <tex>Z\rightarrow (SZX</tex> <br> <tex>S_{1}\endrightarrow XS_{array2}</tex>.# Удалим &epsilon; правила - <br> <tex>\beginS_{array2}{l l} S\rightarrow yX</tex>|-|''2. Удаление <tex>\varepsilon|S</tex>-правил''\\ |<tex>S'\rightarrow A)aS_{1}|S'S'aZ</tex><br> <tex>X\\ Arightarrow aY|bY</tex> <br> <tex>Y\rightarrow (S'aY|bY|(cc</tex> <br> <tex>Z\end{array}rightarrow ZX</tex>.# Удалим цепные правила - <br> <tex>S_{1}\beginrightarrow XS_{array2}|S_{2}</tex> <br> <tex>S_{l l2} S\rightarrow \varepsilonyX|y</tex> |A)-|S'S'\\3. Удаление цепных правил'' |<tex>S'\rightarrow A)aS_{1}|aZ</tex><br> <tex>X\rightarrow aY|S'S'bY</tex> <br> <tex>Y\rightarrow aY|bY|cc</tex> <br> <tex>Z\ Arightarrow ZX</tex> <br> <tex>S_{1}\rightarrow (S'XS_{2}|yX|(\endy</tex> <br> <tex>S_{array2}\rightarrow yX|y</tex>|-|''4.Удаление бесполезных символов''# Заменим терминалы на нетерминалы - |<tex>S\beginrightarrow aS_{array1}</tex> <br> <tex>X\rightarrow aY|bY</tex> <br> <tex>Y\rightarrow aY|bY|cc</tex> <br> <tex>S_{l l1} S\rightarrow XS_{2}|yX|y</tex> <br> <tex>S_{2}\varepsilonrightarrow yX|y</tex>|AB-|S'S'\\5. Уберём ситуации, когда в правиле встречаются несколько терминалов.'' |<tex>S'\rightarrow ABS_{3}S_{1}</tex><br> <tex>X\rightarrow S_{3}Y|S'S'X_{1}Y</tex> <br> <tex>Y\rightarrow S_{3}Y|X_{1}Y|Y_{1}Y_{1}</tex> <br> <tex>S_{1}\ Arightarrow XS_{2}|S_{4}X|y</tex> <br> <tex>S_{2}\rightarrow CS'S_{4}X|(y</tex> <br> <tex>S_{3}\rightarrow a</tex> <br> <tex>S_{4}\ Crightarrow y</tex> <br> <tex>X_{1}\rightarrow (\\ Bb</tex> <br> <tex>Y_{1}\rightarrow )c</tex>\end{array|}<div style="clear:both;"></texdiv>.
== См. также ==
==Источники информации==
* [[wikipedia:en:Chomsky normal form | Wikipedia {{---}} Chomsky normal form]]
* http://www.enseignement.polytechnique.fr/informatique/profs/Luc.Maranget/IF/09/chomsky.pdf* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 280с528с. : ISBN 5-8459-0261-4 (рус.)
275
правок

Навигация