Изменения

=== БлаСхема алгоритма удаления &epsilon;-бла правил из грамматики ===:''Вход.''. КС-грамматика <tex> G=(N,\Sigma, P, S)</tex>.:''Выход.''. Эквивалентная КС-грамматика <tex> G'=(N',\Sigma, P', S) : L(G) = L(G') </tex> без <tex>- {\varepsilon}</tex>-правил.:''МетодСхема алгоритма:''. (:1) Построить Найти все <tex>N_e=\{A \mid A \in Nvarepsilon</tex> и -порождаюшие нетерминалы.:2) Удалить все <tex>A \Rightarrow_{G}^{*}\varepsilon\}</tex>. (2) Построить -правила из <tex>P'</tex> так.: Если 3) Рассмотрим правила вида (*)<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_ealpha_i</tex> для -- последовательности из терминалов и нетерминалов, <tex>1 \leqslant i \leqslant kB_j</tex>, но ни один символ в цепочках -- <tex>a_j (0 \leqslant j \leqslant k) \notin N_e</tex>, то включить в <tex>P'varepsilon</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>\varepsilonB_j</tex>, но не включать добавлять правило <tex>A \rightarrow \varepsilon</tex> (это могло бы произойти в случае. Такое правило может возникнуть, если все <tex>\alpha_i</tex> равны <tex>= \varepsilon</tex>). (3) Если <tex>S \in N_e</tex>, включить в <tex>P'</tex> правила <tex>S' \rightarrow \varepsilon \mid S</tex> где <tex>S'-</tex> новый символ, и положить <tex>N'=N \cup \{ S' \}</tex>. В противном случае положить <tex>N'=N</tex> и <tex>S'=S</tex>. (4) Положить <tex> G'=(N',\Sigma, P', S')</tex>. <tex>\Box</tex>