Изменения

Индукция по длине кратчайшего порождения <tex>A \Rightarrow^* \varepsilon</tex>. Если длина кратчайшего порождения равна <tex>p</tex>, то в множестве <tex>\varepsilon</tex>-порождающих нетерминалов содержатся все нетерминалы, из которых можно вывести пустое слово <tex>\varepsilon</tex> за менее, чем <tex>p</tex> шагов.

'''База.''' <tex>A \Rightarrow \varepsilon</tex>, то есть в грамматике имеется правило <tex>A \rightarrow\varepsilon</tex>. Следовательно, <tex>A</tex> — будет добавлен в множество <tex>\varepsilon</tex>-порождающий нетерминалпорождающих нетерминалов на шаге 1 алгоритма.

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