Изменения

:1) # Если <tex>A \rightarrow \varepsilon</tex> — правило грамматики <tex>G</tex>, то <tex>A</tex> — <tex>\varepsilon</tex>-порождающий нетерминал.:2) # Если <tex>B \rightarrow C_1C_2...C_k</tex> — правило грамматики <tex>G</tex>, где каждый <tex>C_i</tex> — <tex>\varepsilon</tex>-порождающий нетерминал, то <tex>B</tex> — <tex>\varepsilon</tex>-порождающий нетерминал.

|proof = Индукция по длине кратчайшего порождения <tex>A \overset{Rightarrow^*}{\Rightarrow} \varepsilon</tex>:''База.'' <tex>A \overset{Rightarrow^*}{\Rightarrow} \varepsilon</tex> за один шаг, то есть <tex>A \rightarrow\varepsilon</tex>. <tex>\varepsilon</tex>-порождающий нетерминал <tex>A</tex> обнаруживается алгоритмом согласно первому пункту алгоритма.

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