390
правок
Изменения
→Алгоритм удаления ε-правил из грамматики
# Добавить все правила из <tex>P</tex> в <tex>P'</tex>.
# Найти все <tex>\varepsilon</tex>-порождаюшие нетерминалы.
# Для каждого правила вида <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 \leqslant j \leqslant k)</tex>.
# Удалить все <tex>\varepsilon</tex>-правила из <tex>P'</tex>.
# Если в исходной грамматике <tex>\Gamma</tex> выводилось <tex>\varepsilon</tex>, то необходимо добавить новый нетерминал <tex>S'</tex>, сделать его стартовым, добавить правило <tex>S' \rightarrow S|\varepsilon</tex>.
<tex>A \underset{\Gamma'}{\Rightarrow}^*w</tex> тогда и только тогда, когда <tex>A \underset{\Gamma}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex> (*).
<tex>\Rightarrow</tex><br\>
Пусть <tex>A \underset{\Gamma'}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex>.<br/>
Докажем индукцией по длине порождения в грамматике <tex>\Gamma'</tex>, что <tex>A \underset{\Gamma}{\Rightarrow}^*w</tex>.<br/>
