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