Изменения

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

##Если <tex> A \rightarrow w </tex>, причем <tex> w </tex> содержит обнуляемые нетерминалы, то представим <tex> w </tex> в следующем виде <tex> w=w_0 N_0 w_1 N_1 ... w_{n-1} N_{n-1} w_n N_n </tex>, где <tex> N_i </tex> {{---}} вхождение обнуляемого нетерминала, а <tex> w_i </tex> не содержит обнуляемых нетерминалов. Добавим в <tex> \Gamma_2 </tex> все правила, которые можно получить удалением всевозможных комбинаций <tex> N_i </tex> из <tex> w </tex>. Таких вариантов будет <tex> 2^n </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>.   Заметим, что любую контекстно-свободную грамматику можно привести к нормальной форме Хомского. Такая форма очень удобна для работы многих алгоритмов над грамматиками, например, [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ|алгоритм Кока-Янгера-Касами]].}}