Изменения

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

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

Нет изменений в размере, 00:04, 12 ноября 2010
Нет описания правки
(1) Построить <tex>N_e=\{A \mid A \in N</tex> и <tex>A \Rightarrow_{G}^{*}\varepsilon\}</tex>.
(2) Построить <tex>P'</tex> так:
(a) Если <tex>A \rightarrow \alpha_0 B_1 \alpha_1 B_2 \alpha_2 ... B_k \alpha_k \in P, k \geqslant 0</tex> и <tex>B_i \in N_e</tex> для <tex>1 \leqslant i \leqslant k</tex>, но ни один символ в цепочках <tex>a_j (1 0 \leqslant j \leqslant k) \notin N_e</tex>, то включить в <tex>P'</tex> все правила
вида <tex>A \rightarrow \alpha_0 X_1 \alpha_1 X_2 \alpha_2 ... X_k \alpha_k</tex>
где <tex>X_i-</tex> либо <tex>B_i</tex>, либо <tex>\varepsilon</tex>, но не включать правило <tex>A \rightarrow \varepsilon</tex> (это могло бы произойти
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/4774»

Навигация