Изменения
→Алгоритм удаления ε-правил из грамматики
Подставив <tex>S</tex> вместо <tex>A</tex> в утверждение (*), видим, что <tex>w \in L(G)</tex> для <tex>w \ne \varepsilon</tex> тогда и только тогда, когда <tex>w \in L(G')</tex>. Так как после выполнения шага 5 алгоритма в <tex>G'</tex> могло добавиться только пустое слово <tex>\varepsilon</tex>, то язык, задаваемый КС грамматикой <tex>G'</tex>, совпадает с языком, задаваемым КС грамматикой <tex>G</tex>.
}}
=== Пример ===
Рассмотрим грамматику:
<tex>
\begin{array}{l l}
S\rightarrow ABCd\\
A\rightarrow a|\varepsilon\\
B\rightarrow AC\\
C\rightarrow c|\varepsilon
\end{array}
</tex>, в которой <tex>A</tex>, <tex>B</tex> и <tex>C</tex> являются ε-порождающими нетерминалами.
# Переберём для каждого правила все возможные сочетания ε-порождающих нетерминалов и добавим новые правила:
#* <tex>S\rightarrow Ad|ABd|Bd|BCd|Cd|d</tex> для <tex>S \rightarrow ABCd</tex>
#* <tex>B \rightarrow A|C</tex> для <tex>B \rightarrow AC</tex>
# Удалим праила <tex>A\rightarrow \varepsilon</tex> и <tex>C\rightarrow \varepsilon</tex>
В результате мы получим новую грамматику без ε правил:
<tex>\begin{array}{l l}
S\rightarrow Ad|ABd|ABCd|Bd|BCd|Cd|d\\
A\rightarrow a\\
B\rightarrow A|AC|C\\
C\rightarrow c
\end{array}</tex>
== Алгоритм поиска ε-порождающих нетерминалов ==
