Изменения

|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> {{---}} пустая строка, стартовая вершина не содержится в правых частях правил).

==Преобразование Приведение грамматики в нормальную форму к нормальной форме Хомского==

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

# Создание новой стартовой вершиныУберём длинные правила.#: Создадим новую стартовую вершину Воспользуемся [[Удаление длинных правил из грамматики|алгоритмом удаления длинных правил]] из грамматики. Получим грамматику <tex> \Gamma_1 </tex>, эквивалентную исходной, содержащую правила длины <tex> S_0 0, 1</tex> с новым правилом и <tex>2</tex>.# Удаление <tex> S_0 \rightarrow S varepsilon </tex>-правил.#:Воспользуемся [[Удаление eps-правил из грамматики|алгоритмом удаления <tex> \varepsilon </tex>-правил ]] из грамматики. Получим грамматику <tex> \Gamma_2 </tex>, где эквивалентную исходной, но в которой нет <tex> S \varepsilon </tex> {{---}} старая стартовая вершинаправил.# Удаление вершинцепных правил.#:Воспользуемся [[Удаление_цепных_правил_из_грамматики| алгоритмом удаления цепных правил]] из грамматики. Алгоритм работает таким образом, что новые <tex> \varepsilon </tex>-правила не образуются. Получим грамматику <tex> \Gamma_3 </tex>, которые могут породить пустую строкуэквивалентную <tex> \Gamma </tex>.# Удалим бесполезные символы.#: Воспользуемся [[Удаление бесполезных символов из грамматики| алгоритмом удаления бесполезных символов]] из грамматики. Так как <tex> \Gamma_3 </tex> эквивалентна <tex> \Gamma </tex>, то бесполезные символы не могли перестать быть бесполезными. Более того, мы только удаляем правила, новые <tex>\varepsilon</tex>-правила и цепные правила не могли появиться.# Удаление вершинУберём ситуации, которые могут породить друг другакогда в правиле встречаются несколько терминалов.# Преобразование :Для всех правил с длинной правой частьювида <tex> A \rightarrow u_1 u_2</tex> (где <tex> u_i </tex> {{---}} терминал или нетерминал) заменим все терминалы <tex> u_i </tex> на новые нетерминалы <tex> U_i </tex> и добавим правила <tex> U_i \rightarrow u_i </tex>. Теперь правила содержат либо одиночный терминал, либо строку из двух нетерминалов. Таким образом, мы получили грамматику в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma </tex>.

Рассмотрим [[Контекстно-свободные При таком порядке действий размеры грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободную грамматику]] <tex>\Gamma</tex>, из которой удалены [[Удаление бесполезных символов из грамматики|бесполезные символы]], [[Удаление eps-правил из грамматики|<tex>\varepsilon</tex>-правила]], [[Удаление длинных правил из грамматики|длинные правила]] и [[Удаление цепных правил из грамматики|цепные правила]]. Такая грамматика содержит только правила следующего вида:*<tex>A \rightarrow BC</tex>*<tex>A \rightarrow Bc</tex>*<tex>A \rightarrow bC</tex>*<tex>A \rightarrow bc</tex>*<tex>A \rightarrow a</tex>*возможно, <tex>S \rightarrow \varepsilon</tex> (при условии, что <tex>S</tex> не содержится в правых частях правил)Избавимся от правил, в правых частях которых записаны два символа, один из которых является терминалом, то есть правил вида <tex>A \rightarrow Bc</tex>, <tex>A \rightarrow bC</tex> и <tex>A \rightarrow bc</tex>. Введем для каждого терминала <tex>a</tex> "персональный" нетерминал <tex>N_a</tex>. Затем правила вида <tex>A \rightarrow Bc</tex> заменим парой правил <tex>A \rightarrow BN_c</tex> и <tex>N_c \rightarrow c</tex>, правила вида <tex>A \rightarrow bC</tex> заменим парой правил <tex>A \rightarrow N_bC</tex> и <tex>N_b \rightarrow b</tex>, а правила вида <tex>A \rightarrow bc</tex> {{---}} тройкой правил <tex>A \rightarrow N_bN_c</tex>, <tex>N_b \rightarrow b</tex> и <tex>N_c \rightarrow c</tex>возрастают полиномиально.

Теперь у нас остались только После удалении длинных правил из каждого правила вида длины <tex>A k \rightarrow BCgeqslant 3 </tex>, могло появиться <tex>A \rightarrow ak-1 </tex> и, возможно, <tex>S \rightarrow \varepsilon</tex> (при условииновых правил, что <tex>S</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>.}} == Пример =={| 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</tex><br> <tex>Z\rightarrow ZX</tex>|-|''1. Удаление длинных правил''|<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. Удаление <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. Удаление цепных правил''|<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> |-|''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. Уберём ситуации, когда в правиле встречаются несколько терминалов.''|<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</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. — 528с. : ISBN 5-8459-0261-4 (рус.)  [[Категория: Теория формальных языков]][[Категория: Контекстно-Янгерасвободные грамматики]][[Категория: Нормальные формы КС-Касамиграмматик]]