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