271
правка
Изменения
→Преобразование грамматики в нормальную форму Хомского
#:Для каждого правила вида <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>-правила]], [[Удаление длинных правил из грамматики|длинные правила]] и [[Удаление цепных правил из грамматики|цепные правила]]. Такая грамматика содержит только правила следующего вида:
