Изменения

Рассмотрим вывод <tex>w</tex> в <tex>L(\Gamma')\cup \Gamma</tex>, минимальный по количеству примененных правил, отсутствующих в <tex>\Gamma</tex>.<br>Найдем в этом выводе первое применение правила <tex>A \rightarrow a_1A_1, a_1 \in \Sigma \cup N</tex>, которого нет в <tex>\Gamma</tex>. В ходе алгоритма оно это правило было получено из некоторого длинного правила <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>. Применим правило <tex>A \rightarrow a_1 a_2 \ldots a_k</tex> вместо <tex>A \rightarrow a_1A_1</tex>, и удалим в выводе все применения правил, полученных из <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>.Такое преобразование уменьшит в выводе Получим вывод <tex>w</tex> количество правил, которых нет в <tex>\Gamma\cup \Gamma'</tex>. Будем повторять это преобразование, пока не получим вывод <tex>w</tex> в котором меньше применений правил, отсутствующих в <tex>\Gamma</tex>, чем в исходном. Противоречие.