Бюрократы, editor, Администраторы
422
правки
Изменения
м
Нет описания правки
== Алгоритм удаления ε-правил из грамматики ==
'''Вход:''' КС грамматика <tex> G=\langle N,\Sigma, P, S \rangle</tex>.<br/>
'''Выход:''' КС грамматика <tex> G'=\langle N,\Sigma, P', S \rangle : L(G') = L(G) \setminus \mathcal {f} lbrace \varepsilon \mathcal {g}rbrace</tex>.
# [[#.D0.90.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC_.D0.BF.D0.BE.D0.B8.D1.81.D0.BA.D0.B0_.CE.B5-.D0.BF.D0.BE.D1.80.D0.BE.D0.B6.D0.B4.D0.B0.D1.8E.D1.89.D0.B8.D1.85_.D0.BD.D0.B5.D1.82.D0.B5.D1.80.D0.BC.D0.B8.D0.BD.D0.B0.D0.BB.D0.BE.D0.B2 | Найти все <tex>\varepsilon</tex>-порождаюшие нетерминалы]].
=== Доказательство корректности ===
{{Теорема
|statement = Если грамматика <tex>G'</tex> была построена с помощью описанного выше алгоритма по грамматике <tex>G</tex>, то <tex>L(G') = L(G) \setminus \mathcal {f}lbrace\varepsilon \mathcal {g}rbrace</tex>.
|proof =
Для этого достаточно доказать, что
