Изменения

Для простоты доказательства можно считать, что на <tex>k</tex>-й итерации алгоритма в множество <tex>\varepsilon</tex>-порождающих нетерминалов добавляются только нетерминалы <tex>A : A \Rightarrow^* \varepsilon</tex> за <tex>k</tex> шагов. Пусть после очередной итерации завершения алгоритма множество <tex>\varepsilon</tex>-порождающих нетерминалов не изменилось. Пусть существуют нетерминалы такие, что они является являются <tex>\varepsilon</tex>-порождающими, но не были найдены алгоритмом. Выберем из этих нетерминалов нетерминал <tex>B : B \Rightarrow^* \varepsilon</tex> за минимальное количество шагов. Тогда, в грамматике есть правило <tex>B \rightarrow C_1C_2...C_k</tex>, где каждый <tex>C_i</tex> входит в множество <tex>\varepsilon</tex>-порождающих нетерминалов, так как иначе вместо <tex>B</tex> необходимо было взять <tex>C_i</tex>. Следовательно, на одной из итераций алгоритма <tex>B</tex> уже добавится добавился в множество <tex>\varepsilon</tex>-порождающих нетерминалов. Получили противоречие. Следовательно, алгоритм находит все <tex>\varepsilon</tex>-порождающие нетерминалы.