Изменения
→Алгоритм поиска ε-порождающих нетерминалов
Пусть после завершения алгоритма существуют нетерминалы такие, что они являются <tex>\varepsilon</tex>-порождающими, но не были найдены алгоритмом. Выберем из этих нетерминалов нетерминал <tex>B</tex>, из которого выводится <tex>\varepsilon</tex> за наименьшее число шагов. Тогда в грамматике есть правило <tex>B \rightarrow C_1C_2...C_k</tex>, где каждый нетерминал <tex>C_i</tex> — <tex>\varepsilon</tex>-порождающий. Каждый <tex>C_i</tex> входит в множество <tex>\varepsilon</tex>-порождающих нетерминалов, так как иначе вместо <tex>B</tex> необходимо было взять <tex>C_i</tex>. Следовательно, на одной из итераций алгоритма <tex>B</tex> уже добавился в множество <tex>\varepsilon</tex>-порождающих нетерминалов. Противоречие. Следовательно, алгоритм находит все <tex>\varepsilon</tex>-порождающие нетерминалы.
}}
=== Пример ===
Рассмотрим грамматику:
<tex>
\begin{array}{l l}
S\rightarrow ABC|DS\\
A\rightarrow \varepsilon\\
B\rightarrow AC\\
C\rightarrow \varepsilon\\
D\rightarrow d
\end{array}
</tex>
# Возьмём множество состоящее ε-порождающих нетерминалов <tex>\lbrace A, C \rbrace</tex>.
# Добавим <tex>B</tex> в множество, так как правая часть правила <tex>B\rightarrow AC</tex> состоит только из нетерминалов из множества.
# Повторим второй пункт для правила <tex>S\rightarrow ABC</tex> и получим множество <tex>\lbrace A, B, C, S \rbrace</tex>.
# Больше нету нерассмотренных правил, содержащих справа только нетерминалы из множества.
Таким образом ε-порождающими нетерминалами являются <tex>A</tex>, <tex>B</tex>, <tex>C</tex> и <tex>S</tex>.
== Литература ==
