Изменения

Перейти к: навигация, поиск

Удаление eps-правил из грамматики

Нет изменений в размере, 20:02, 6 декабря 2011
м
Нет описания правки
'''Выход:''' КС грамматика <tex> G'=\langle N,\Sigma, P', S \rangle</tex> без <tex>\varepsilon</tex>-правил (возможно правило <tex>S \rightarrow \varepsilon</tex>, но в этом случае <tex>S</tex> не встречается в правых частях правил). <tex>L(G') = L(G)</tex>.
# Добавить все правила из <tex>P</tex> в <tex>P'</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>-порождаюшие нетерминалы]].
# Добавить все правила из <tex>P</tex> в <tex>P'</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 \le j \le k)</tex>.
# Удалить все <tex>\varepsilon</tex>-правила из <tex>P'</tex>.

Навигация