Изменения

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

#: Воспользуемся [[Удаление длинных правил из грамматики|алгоритмом удаления длинных правил]] из грамматики. Получим грамматику <tex> \Gamma_1 </tex>, эквивалентную исходной, содержащую правила длины 0, 1 и 2.

# Удаление <tex> \varepsilon </tex>-правил.

# Удалим бесполезные символы.

#:Воспользуемся [[Удаление бесполезных символов из грамматики| алгоритмом удаления бесполезных символов]] из грамматики. Так как <tex> \Gamma_3 </tex> эквивалентна <tex> \Gamma </tex>, то бесполезные символы не могли перестать быть бесполезными. Более того, мы только удаляем правила, новые <tex>\varepsilon</tex>-правила и цепные правила не могли появиться.

#:Для всех правил вида <tex> A \rightarrow u_1 u_2 ... u_n </tex> (где <tex> n \ge 2 </tex>, <tex> u_i </tex> {{---}} терминал или нетерминал) заменим все терминалы <tex> u_i </tex> на переменные <tex> U_i </tex> и добавим правила <tex> U_i \rightarrow u_i </tex>. Теперь правила содержат либо одиночный терминал, либо строку из нетерминалов.

Таким образом, мы получили грамматику в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma </tex>.