Изменения

После пятого шага грамматика <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>.

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