Изменения

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