==Преобразование грамматики в нормальную форму Хомского==
Рассмотрим [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободную грамматику]] <tex> \Gamma </tex>. Для преобразования ее в нормальную форму Хомского необходимо выполнить 5 шагов. Каждый шаг работает c преобразованной грамматикойНа каждом шаге мы строим новую <tex> \Gamma_i </tex>, которая допускает тот же язык, что и <tex> \Gamma </tex>.
# Создание новой стартовой вершины.
#: Создадим новую стартовую вершину <tex> S_0 </tex> с новым правилом <tex> S_0 \rightarrow S </tex>, где <tex> S </tex> {{---}} старая стартовая вершина. Получим Добавим в <tex> \Gamma_1 </tex> эту вершину, правило и <tex> \Gamma </tex>.
# Удаление <tex> \varepsilon </tex>-правил.
##Если <tex> A \rightarrow \varepsilon </tex>, то выкинем такое правило.
#:Для каждого правила вида <tex> A \rightarrow B_0 B_1 ... B_n </tex>, где <tex> n \ge 2 </tex>, добавим новые нетерминалы <tex> A_1, A_2, ... , A_{n-2} </tex> и правила <tex> A \rightarrow B_1 A_1 </tex>, <tex> A_1 \rightarrow B_2 A_2 </tex>, <tex> A_2 \rightarrow B_3 A_3 </tex>, <tex> ... </tex> , <tex> A_{n-2} \rightarrow B_{n-1} B_n </tex> в <tex> \Gamma_5 </tex>.
После пятого шага грамматика <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>.
Рассмотрим [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободную грамматику]] <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 \rightarrow BC</tex>, <tex>A \rightarrow a</tex> и, возможно, <tex>S \rightarrow \varepsilon</tex> (при условии, что <tex>S</tex> не содержится в правых частях правил). Грамматика, содержащая правила только такого вида, называется грамматикой в '''нормальной форме Хомского'''. Заметим, что любую контекстно-свободную грамматику можно привести к нормальной форме Хомского. Такая форма грамматики очень удобна для работы многих алгоритмов над грамматиками, например, [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ|алгоритм Кока-Янгера-Касами]].
