275
правок
Изменения
м
# Удаление <tex> \varepsilon </tex>-правил.
#:Воспользуемся [[Удаление eps-правил из грамматики|алгоритмом удаления <tex> \varepsilon </tex>-правил ]] из грамматики. Получим грамматику <tex> \Gamma_2 </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>.# Удалим ε правила - <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>.
* http://www.enseignement.polytechnique.fr/informatique/profs/Luc.Maranget/IF/09/chomsky.pdf* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 280с528с. : ISBN 5-8459-0261-4 (рус.)
→Источники информации
{{Определение
|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_1
</tex>, эквивалентную исходной, содержащую правила длины <tex>0, 1</tex> и <tex>2</tex>.
# Удаление <tex> \varepsilon </tex>-правил.
#:Воспользуемся [[Удаление eps-правил из грамматики|алгоритмом удаления <tex> \varepsilon </tex>-правил ]] из грамматики. Получим грамматику <tex> \Gamma_2 </tex>, эквивалентную исходной, но в которой нет <tex>\varepsilon </tex>-правил.
# Удаление цепных правил.
#:Воспользуемся [[Удаление_цепных_правил_из_грамматики| алгоритмом удаления цепных правил]] из грамматики. Алгоритм работает таким образом, что новые <tex> \varepsilon </tex>-правила не образуются. Получим грамматику <tex> \Gamma_3 </tex>, эквивалентную <tex> \Gamma </tex>.
# Удалим бесполезные символы.
#:Воспользуемся [[Удаление бесполезных символов из грамматики| алгоритмом удаления бесполезных символов]] из грамматики. Так как <tex> \Gamma_3 </tex> эквивалентна <tex> \Gamma </tex>, то бесполезные символы не могли перестать быть бесполезными. Более того, мы только удаляем правила, новые <tex>\varepsilon</tex>-правила и цепные правила не могли появиться.
Таким образом, мы получили грамматику в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma </tex>.
Стоит заметить, что порядок выполнения операции операций важен. Первое правило должно быть обязательно выполнено перед третьимвторым, иначе время нормализации ухудшится до <tex>O(2^{\left| \Gamma \right|})</tex>. Третье правило идет после второго, потому что после удаления <tex>\varepsilon</tex>-правил, могут образоваться новые цепные правила. Также четвертое правило должно быть выполнено после позже третьего и второго и третьего, так как второе и третье правила они могут порождать бесполезные символы.
При таком порядке действий размеры грамматики возрастают полиномиально.
== Пример ==
== См. также ==
==Источники информации==
* [[wikipedia:en:Chomsky normal form | Wikipedia {{---}} Chomsky normal form]]
