Изменения

|definition=Грамматикой в '''нормальной форме Хомского''' (англ. ''Chomsky normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержатся содержаться правила только следующего вида::<tex>A \rightarrow B C </tex>,

:<tex>A \rightarrow a </tex>,

:<tex>S \rightarrow \varepsilon </tex>,

Рассмотрим контекстно-свободную грамматику <tex> \Gamma </tex>. Для приведения ее к нормальной форме Хомского необходимо выполнить четыре шагапять шагов. На каждом шаге мы строим новую <tex> \Gamma_i </tex>, которая допускает тот же язык, что и <tex> \Gamma </tex>.

##:Воспользуемся [[Удаление eps-правил из грамматики|алгоритмом удаления <tex> \varepsilon </tex>-правил ]] из грамматики. Получим грамматику <tex> \Gamma_1 Gamma_2 </tex>.# Преобразование узловых пар.#:Для каждой узловой пары <tex> (A, B) </tex>эквивалентную исходной, найдем все правила но в которой нет <tex> B \rightarrow w varepsilon </tex>-правил.# Удаление цепных правил.#:Воспользуемся [[Удаление_цепных_правил_из_грамматики| алгоритмом удаления цепных правил]] из грамматики. Алгоритм работает таким образом, где что новые <tex> w \varepsilon </tex> {{---}} произвольная строка терминалов и нетерминалов, и добавим правила не образуются. Получим грамматику <tex> A \rightarrow w Gamma_3 </tex> в , эквивалентную <tex> \Gamma_2 Gamma </tex>.# Преобразование смешанных правилУдалим бесполезные символы. #:Если Воспользуемся [[Удаление бесполезных символов из грамматики| алгоритмом удаления бесполезных символов]] из грамматики. Так как <tex> A \rightarrow w Gamma_3 </tex> {{---}} смешанное правило, то можно представить эквивалентна <tex> w \Gamma </tex> в виде <tex> w=v_0 c_1 v_1 c_2 , то бесполезные символы не могли перестать быть бесполезными... v_{n-1} c_n v_n </tex>Более того, мы только удаляем правила, где новые <tex> v_i \varepsilon</tex> {{---}} строка нетерминаловправила и цепные правила не могли появиться.# Уберём ситуации, а <tex> c_i </tex> является терминаломкогда в правиле встречаются несколько терминалов. Тогда для каждого #:Для всех правил вида <tex> c_i </tex> добавим нетерминал <tex> C_i </tex> и правило <tex> C_i A \rightarrow c_i u_1 u_2</tex> в (где <tex> \Gamma_3 u_i </tex>. Получим {{---}} терминал или нетерминал) заменим все терминалы <tex> w'=v_0 C_1 v_1 C_2 ... v_{n-1} C_n v_n u_i </tex>. Добавим правило на новые нетерминалы <tex> A \rightarrow w' U_i </tex> в и добавим правила <tex> U_i \Gamma_3 rightarrow u_i </tex>. # Преобразование длинных правилТеперь правила содержат либо одиночный терминал, либо строку из двух нетерминалов.#:Воспользуемся [[Удаление длинных правил из грамматики|алгоритмом удаления длинных правил]] из грамматики. Получим Таким образом, мы получили грамматику в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma_4 Gamma </tex>.

Таким образом мы получили грамматику Стоит заметить, что порядок выполнения операций важен. Первое правило должно быть выполнено перед вторым, иначе время нормализации ухудшится до <tex>O(2^{\left| \Gamma \right|})</tex>. Третье правило идет после второго, потому что после удаления <tex>\varepsilon</tex>-правил, могут образоваться новые цепные правила. Также четвертое правило должно быть выполнено позже третьего и второго, так как они могут порождать бесполезные символы. При таком порядке действий размеры грамматики возрастают полиномиально. После удалении длинных правил из каждого правила длины <tex> k \geqslant 3 </tex> могло появиться <tex> k-1 </tex> новых правил, причем их длина не превышает двух. На этом шаге размер грамматики возрастает не более, чем вдвое. При удалении <tex> \Gamma_4 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> \Gamma Sigma</tex> {{---}} алфавит грамматики) новых правил, причем все они будут длины <tex>1</tex>.

==ЛитератураПример ==* http{| 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|cc</wwwtex><br> <tex>Z\rightarrow ZX</tex>|-|''1.enseignementУдаление длинных правил''|<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>|-|''2.polytechniqueУдаление <tex>\varepsilon</tex>-правил''|<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> |-|''3.frУдаление цепных правил''|<tex>S\rightarrow aS_{1}|aZ</informatiquetex><br> <tex>X\rightarrow aY|bY</profstex> <br> <tex>Y\rightarrow aY|bY|cc</Luctex> <br> <tex>Z\rightarrow ZX</tex> <br> <tex>S_{1}\rightarrow XS_{2}|yX|y</tex> <br> <tex>S_{2}\rightarrow yX|y</tex> |-|''4. Удаление бесполезных символов''|<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>|-|''5. Уберём ситуации, когда в правиле встречаются несколько терминалов.Maranget''|<tex>S\rightarrow S_{3}S_{1}</tex><br> <tex>X\rightarrow S_{3}Y|X_{1}Y</tex> <br> <tex>Y\rightarrow S_{3}Y|X_{1}Y|Y_{1}Y_{1}</tex> <br> <tex>S_{1}\rightarrow XS_{2}|S_{4}X|y</tex> <br> <tex>S_{2}\rightarrow S_{4}X|y</tex> <br> <tex>S_{3}\rightarrow a</tex> <br> <tex>S_{4}\rightarrow y</IFtex> <br> <tex>X_{1}\rightarrow b</09tex> <br> <tex>Y_{1}\rightarrow c</chomskytex>|}<div style="clear:both;"></div> == См.pdfтакже ==* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]* [[Нормальная_форма_Куроды | Нормальная форма Куроды]]* [[Приведение_грамматики_к_ослабленной_нормальной_форме_Грейбах | Приведение грамматики к ослабленной нормальной форме Грейбах]] ==Источники информации==* [[wikipedia:en:Chomsky normal form | Wikipedia {{---}} Chomsky normal form]]* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528с. : ISBN 5-8459-0261-4 (рус.)  [[Категория: Теория формальных языков]][[Категория: Контекстно-свободные грамматики]][[Категория: Нормальные формы КС-грамматик]]