Изменения

Для простоты доказательства можно считать, что на <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^* \varepsilonrightarrow C_1C_2...C_k</tex> ровно за , где каждый <tex>nC_i</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>-порождающие нетерминалы.