Изменения
Нет описания правки
Получим вывод <tex>w</tex> в <tex>\Gamma \cup \Gamma'</tex>, в котором меньше применений правил, отсутствующих в <tex>\Gamma</tex>, чем в исходном. Противоречие.
}}
== Время работы алгоритма ==
Данный алгоритм работает за <tex>O(\left| \Gamma \right|)</tex> и добавляет в грамматику <tex>O(\left| \Gamma \right|)</tex> новых правил длинны <tex>O(1)</tex>.
== Пример работы ==
<tex>B \rightarrow dB_1</tex>, <br>
<tex>B_1 \rightarrow ef</tex>. <br>
== См. также ==
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]
* [http://en.wikipedia.org/wiki/Chomsky_normal_form Chomsky normal form]
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
