Изменения
→Поиск ε-порождающих нетерминалов
''Схема алгоритма:''
# Построить граф <tex>Gr = (V = N, E = \mathcal {f} (A, B) | A \rightarrow \alpha B \beta \mathcal {g})</tex>, где <tex>\alpha, \beta</tex> состоят из нетерминалов.
{{Теорема
# в грамматике <tex>G</tex> есть правило <tex>A \rightarrow C_1C_2...C_k</tex>, где каждый <tex>C_i</tex> — <tex>\varepsilon</tex>-порождающий нетерминал.
|proof = Индукция по длине кратчайшего порождения <tex>A \Rightarrow^* \varepsilon</tex>
:''База.'' <tex>A \Rightarrow^* \varepsilon</tex> за один шаг, то есть правило <tex>A \rightarrow\varepsilon</tex>. Следовательно <tex>А - A</tex> — <tex>\varepsilon</tex>-порождающий нетерминал.
:''Индукция.'' Пусть <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>-порождающий.
}}
