205
правок
Изменения
м
→Схема алгоритма удаления ε-правил из грамматики
:2) Удалить все <tex>\varepsilon</tex>-правила из <tex>P</tex>.
:3) Рассмотрим правила вида (*)<tex>A \rightarrow \alpha_0 B_1 \alpha_1 B_2 \alpha_2 ... B_k \alpha_k</tex>, где <tex>\alpha_i</tex> — последовательности из терминалов и нетерминалов, <tex>B_j</tex> — <tex>\varepsilon</tex>-порождающие нетерминалы. Добавить все возможные правила вида (*), в которых либо присутствует, либо отсутствует <tex>B_j</tex>, кроме правила <tex>A \rightarrow \varepsilon</tex>. Такое правило может возникнуть, если все <tex>\alpha_i = \varepsilon</tex>.
''Замечание''
Если в исходной грамматике <tex>G</tex> есть правило <tex>S \rightarrow \varepsilon</tex> и <tex>S</tex> встречается в правых частях, то для того, чтобы получить эквивалентную грамматику без <tex>\varepsilon</tex>-правил, необходимо после применения описанного выше алгоритма добавить новый нетерминал <tex>S'</tex>, сделать его стартовым, добавить правила <tex>S' \rightarrow S|\varepsilon</tex>.
== Доказательство корректности алгоритма ==
