editor
177
правок
Изменения
м
→Алгоритм удаления ε-правил из грамматики
# Для каждого правила вида <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>P'</tex> все возможные варианты правил, в которых либо присутствует, либо удалён каждый из нетерминалов <tex>B_j\; (1 \le j \le k)</tex>.
# Удалить все <tex>\varepsilon</tex>-правила из <tex>P'</tex>.
# Если в исходной грамматике <tex>G</tex> выводилось <tex>\varepsilon</tex>, то необходимо добавить новый нетерминал <tex>S'</tex>, сделать его стартовым, добавить правил правило <tex>S' \rightarrow S|\varepsilon</tex>.
=== Доказательство корректности ===
