Изменения

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

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

Если # Уберём длинные правила.#: Воспользуемся [[Удаление длинных правил из грамматики|алгоритмом удаления длинных правил]] из грамматики. Получим грамматику <tex> \Gamma_1 </tex>, эквивалентную исходной, содержащую правила длины <tex>0, 1</tex> и <tex>2</tex>.# Удаление <tex> \varepsilon </tex>-правил.#:Воспользуемся [[Удаление eps-правил из грамматики|алгоритмом удаления <tex> \varepsilon </tex>-правил ]] из грамматики. Получим грамматику <tex> \Gamma_2 </tex>, эквивалентную исходной, но в которой нет <tex> A \rightarrow B_1varepsilon </tex>-правил.# Удаление цепных правил.#:Воспользуемся [[Удаление_цепных_правил_из_грамматики| алгоритмом удаления цепных правил]] из грамматики.Алгоритм работает таким образом, что новые <tex> \varepsilon </tex>-правила не образуются.B_n Получим грамматику <tex> \Gamma_3 </tex>, где все эквивалентную <tex> \Gamma </tex>.# Удалим бесполезные символы.#:Воспользуемся [[Удаление бесполезных символов из грамматики| алгоритмом удаления бесполезных символов]] из грамматики. Так как <tex> \Gamma_3 </tex> эквивалентна <tex> B_i \Gamma </tex> обнуляемые, то бесполезные символы не могли перестать быть бесполезными. Более того, мы только удаляем правила, новые <tex> A \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>.

{{Определение|definition=Пара нетерминалов Стоит заметить, что порядок выполнения операций важен. Первое правило должно быть выполнено перед вторым, иначе время нормализации ухудшится до <tex> A </tex> и <tex> B O(2^{\left| \Gamma \right|})</tex> называется узловой. Третье правило идет после второго, если потому что после удаления <tex> A \Rightarrow^* B varepsilon</tex>-правил, могут образоваться новые цепные правила. Также четвертое правило должно быть выполнено позже третьего и второго, так как они могут порождать бесполезные символы.

<tex> \forall A </tex> выполняется <tex> (A, A) </tex> {{---}} узловая параПри таком порядке действий размеры грамматики возрастают полиномиально.

Если После удалении длинных правил из каждого правила длины <tex> (A, B) k \geqslant 3 </tex> {{---}} узловая пара, а могло появиться <tex> B \rightarrow C k-1 </tex>новых правил, то <tex> (Aпричем их длина не превышает двух. На этом шаге размер грамматики возрастает не более, C) </tex> тоже узловая парачем вдвое.}}

{{Определение|definition=Правило При удалении <tex> A \rightarrow w varepsilon </tex> называется смешанным-правил из грамматики, если содержащей правила длины <tex> w 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> |\Gamma Sigma|</tex>. Для преобразования ее в нормальную форму Хомского необходимо выполнить 5 шагов. На каждом шаге мы строим новую (<tex> \Gamma_i Sigma</tex>{{---}} алфавит грамматики) новых правил, которая допускает тот же язык, что и причем все они будут длины <tex> \Gamma 1</tex>.}}

== Пример =={| border="1" class="wikitable" style="width: 500px; height: 500px; float: left;"!style="background:#41aef0"|Текущий шаг!style="background:# Создание новой стартовой вершины41aef0"|Грамматика после применения правила|-|''0.Исходная грамматика''#: Создадим новую стартовую вершину |<tex> S_0 S\rightarrow aXbX|aZ</tex> с новым правилом <br> <tex> S_0 X\rightarrow S aY|bY|\varepsilon</tex>, где <tex> S </texbr> {{---}} старая стартовая вершина. Добавим в <tex> Y\Gamma_1 rightarrow X|cc</tex> эту вершину, правило и <texbr> \Gamma </tex>.# Удаление <tex> Z\varepsilon rightarrow ZX</tex>|-правил.##Если <tex> A \rightarrow \varepsilon </tex>, то выкинем такое правило|''1.Удаление длинных правил''##Если |<tex> A S\rightarrow w aS_{1}|aZ</tex>, где <texbr> w </tex> не содержит <tex> X\rightarrow aY|bY|\varepsilon </tex> и обнуляемых нетерминалов, то добавим такое правило в <tex> \Gamma_2 </texbr>.##Если <tex> A Y\rightarrow w X|cc</tex>, причем <texbr> w </tex> содержит обнуляемые нетерминалы, то представим Z\rightarrow ZX</tex> w </texbr> в следующем виде <tex> w=w_0 N_0 w_1 N_1 ... w_S_{n-1} N_\rightarrow XS_{n-12} w_n N_n </tex>, где <texbr> N_i </tex> S_{{---2}} вхождение обнуляемого нетерминала, <tex> w_i \rightarrow yX</tex> не содержит обнуляемых нетерминалов|-|''2. Добавим в Удаление <tex> \Gamma_2 varepsilon</tex> все правила, которые можно получить удалением всевозможных комбинаций -правил''|<tex> N_i S\rightarrow aS_{1}|aZ</tex> из <br> <tex> w X\rightarrow aY|bY</tex>. Таких вариантов будет <br> <tex> 2^n Y\rightarrow aY|bY|cc</tex>. #:Если стартовая вершина <br> <tex> Z\Gamma_1 rightarrow ZX</tex> является обнуляемой, то добавим в <br> <tex> S_{1}\Gamma_2 rightarrow XS_{2}|S_{2}</tex> правило <br> <tex> S_0 S_{2}\rightarrow \varepsilon yX|y</tex>.# Преобразование узловых пар|-|''3.Удаление цепных правил''#:Для каждой узловой пары |<tex> (A, B) S\rightarrow aS_{1}|aZ</tex>, найдем все правила <br> <tex> B X\rightarrow w aY|bY</tex>, где <tex> w </texbr> {{---}} произвольная строка терминалов и нетерминалов, и добавим <tex> A Y\rightarrow w aY|bY|cc</tex> в <br> <tex> Z\Gamma_3 rightarrow ZX</tex>.# Преобразование смешанных правил.#:Если <texbr> A \rightarrow w </tex> S_{1}\rightarrow XS_{---}2} смешанное правило, то можно представить |yX|y</tex> w </texbr> в виде <tex> w=v_0 c_1 v_1 c_2 ... v_S_{n-12} c_n v_n \rightarrow yX|y</tex>, где |-|''4. Удаление бесполезных символов''|<tex> v_i S\rightarrow aS_{1}</tex> {{---}} строка нетерминалов, а <br> <tex> c_i X\rightarrow aY|bY</tex> является терминалом. Тогда для каждого <texbr> c_i </tex> добавим нетерминал Y\rightarrow aY|bY|cc</tex> C_i </texbr> и правило <tex> C_i S_{1}\rightarrow c_i XS_{2}|yX|y</tex> в <br> <tex> S_{2}\Gamma_4 rightarrow yX|y</tex>|-|''5. Уберём ситуации, когда в правиле встречаются несколько терминалов. Получим ''|<tex> w'=v_0 C_1 v_1 C_2 ... vS\rightarrow S_{3}S_{n-1} C_n v_n </tex>. Добавим правило <br> <tex> A X\rightarrow w' S_{3}Y|X_{1}Y</tex> в <texbr> \Gamma_4 </tex>. # Преобразование длинных правил.#:Для каждого правила вида <tex> A Y\rightarrow B_0 B_1 ... B_n S_{3}Y|X_{1}Y|Y_{1}Y_{1}</tex>, где <br> <tex> n S_{1}\ge rightarrow XS_{2 }|S_{4}X|y</tex>, добавим новые нетерминалы <br> <tex> A_1, A_2, ... , A_S_{n-2} \rightarrow S_{4}X|y</tex> и правила <br> <tex> A S_{3}\rightarrow B_1 A_1 a</tex>, <br> <tex> A_1 S_{4}\rightarrow B_2 A_2 y</tex>, <br> <tex> A_2 X_{1}\rightarrow B_3 A_3 b</tex>, <texbr> ... </tex> , <tex> A_Y_{n-21} \rightarrow B_{n-1} B_n c</tex> в |}<texdiv style="clear:both;"> \Gamma_5 </texdiv>.

После пятого шага грамматика <tex> \Gamma_5 </tex> содержит только правила вида <tex> A \rightarrow B C </tex> и <tex> A \rightarrow a </tex>== См. также ==* [[Контекстно-свободные_грамматики, где <tex> A_вывод, B, C </tex> {{_лево---}} нетерминалы_и_правосторонний_вывод, <tex> a </tex> {{--_дерево_разбора|Контекстно-}} терминал. Возможно, что также присутствует правило <tex> S_0 \rightarrow \varepsilon </tex>. Новая грамматика допускает тот же язык, что и <tex> \Gamma </tex>.свободные грамматики]]* [[Нормальная_форма_Куроды | Нормальная форма Куроды]]* [[Приведение_грамматики_к_ослабленной_нормальной_форме_Грейбах | Приведение грамматики к ослабленной нормальной форме Грейбах]]

Заметим, что любую контекстно[[Категория: Теория формальных языков]][[Категория: Контекстно-свободную грамматику можно привести к нормальной форме Хомского. Такая форма свободные грамматики очень удобна для работы многих алгоритмов над грамматиками, например, ]][[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ|алгоритм Кока-ЯнгераКатегория: Нормальные формы КС-Касамиграмматик]].