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

Основные определения

Определение:

Правила вида [math]A \to \varepsilon[/math] называются [math]\varepsilon[/math]-правилами.

Определение:

Назовем КС-грамматику [math]G=(N,\Sigma, P, S)[/math] грамматикой без [math]\varepsilon[/math]-правил (или неукорачивающей), если либо (1) [math]P[/math] не содержит [math]\varepsilon[/math]-правил, либо (2) есть точно одно [math]\varepsilon[/math]-правило [math]S \to \varepsilon[/math] и [math]S[/math] не встречается в правых частях остальных правил из [math]P[/math].

По данной произвольной КС-грамматике [math]G[/math] часто бывает удобно строить новую КС-грамматику [math]G'[/math] без [math]\varepsilon[/math]-правил, эквивалентную исходной.

Алгоритм удаления ε-правил

Вход. КС-грамматика [math] G=(N,\Sigma, P, S)[/math].

Выход. Эквивалентная КС-грамматика [math] G'=(N',\Sigma, P', S') [/math] без [math]\varepsilon[/math]-правил.

Метод.

   (1) Построить [math]N_e=\{A \mid A \in N[/math] и [math]A \Rightarrow_{G}^{*}\varepsilon\}[/math].
   (2) Построить [math]P'[/math] так:
           Если [math]A \rightarrow \alpha_0 B_1 \alpha_1 B_2 \alpha_2 ... B_k \alpha_k   \in P, k \geqslant 0[/math] и [math]B_i \in N_e[/math] для [math]1 \leqslant i \leqslant k[/math],
           но ни один символ в цепочках [math]a_j (0 \leqslant j \leqslant k) \notin N_e[/math], то включить в [math]P'[/math] все правила
           вида [math]A \rightarrow \alpha_0 X_1 \alpha_1 X_2 \alpha_2 ... X_k \alpha_k[/math]
           где [math]X_i-[/math] либо [math]B_i[/math], либо [math]\varepsilon[/math], но не включать правило [math]A \rightarrow \varepsilon[/math] (это могло бы произойти 
           в случае, если все [math]\alpha_i[/math] равны [math]\varepsilon[/math]).
    (3) Если [math]S \in N_e[/math], включить в [math]P'[/math] правила
                               [math]S' \rightarrow \varepsilon \mid S[/math]
        где [math]S'-[/math] новый символ, и положить [math]N'=N \cup \{ S' \}[/math]. В противном случае 
        положить [math]N'=N[/math] и [math]S'=S[/math].
    (4) Положить [math] G'=(N',\Sigma, P', S')[/math]. [math]\Box[/math]

Для доказательства корректности нам понадобиться следующее утверждение:

Утверждение:

[math]A \overset{*}{\underset{G'}{\Rightarrow}}w[/math] [math](A \ne S')[/math]  тогда и только тогда, когда [math]A \overset{*}{\underset{G}{\Rightarrow}}w[/math]  и  [math]w \ne \varepsilon[/math]

[math]\triangleright[/math]

[math]\Rightarrow[/math]<br\> Пусть [math]A \overset{*}{\underset{G'}{\Rightarrow}}w[/math]. Несомненно, [math]w \ne \varepsilon[/math], поскольку [math]G'[/math] - грамматика без [math]\varepsilon[/math]-правил и [math]A \ne S'[/math]. Докажем индукцией по длине порождения, что [math]A \overset{*}{\underset{G}{\Rightarrow}}w[/math]. Обозначим длину порождения за [math]p[/math]. Базис. [math]p = 1[/math] В этом случае в [math]G'[/math] есть правило [math]A \rightarrow w[/math]. Согласно конструкции [math]G'[/math] в [math]G[/math] есть правило [math]A \rightarrow \alpha[/math], причем [math]\alpha-[/math] это [math]w[/math], символы которой, возможно, перемежаются [math]\varepsilon-[/math] порождающими переменными. Тогда в [math]G[/math] есть порождения [math]A \underset{G}{\Rightarrow} \alpha \overset{*}{\underset{G}{\Rightarrow}}w[/math], где на шагах после первого, из всех переменных в цепочке [math]\alpha[/math] выводиться [math]\varepsilon[/math]. Предположение. Пусть [math][A \overset{*}{\underset{G'}{\Rightarrow}}w[/math] [math](A \ne S')][/math]  [math]\Rightarrow [A \overset{*}{\underset{G}{\Rightarrow}}w[/math]  и  [math]w \ne \varepsilon][/math] верно для [math]p \lt n[/math]. Переход. [math]p = n[/math] Пусть в порождении [math]n[/math] шагов, [math]n \gt 1[/math]. Тогда оно имеет вид [math]A\underset{G'}{\Rightarrow}X_1 X_2...X_k \overset{*}{\underset{G'}{\Rightarrow}}w[/math], где [math]X_i \in N \cup \Sigma [/math]. Первое использованное правило должно быть построено по правилу [math]A \rightarrow Y_1 Y_2...Y_m[/math], где цепочка [math]Y_1 Y_2...Y_m[/math] совпадает с цепочкой [math]X_1 X_2...X_k[/math], цепочка [math]Y_1 Y_2...Y_m[/math], возможно, перемежаются [math]\varepsilon-[/math] порождающими переменными. Цепочку [math]w[/math] можно разбить на [math]w_1 w_2...w_k[/math], где [math]X_i \overset{*}{\underset{G'}{\Rightarrow}}w_i[/math]. Если [math]X_i[/math] есть терминал, то [math]w = X_i[/math], a если переменная, то порождение [math]X_i \overset{*}{\underset{G'}{\Rightarrow}}w_i[/math] содержит менее [math]n[/math] шагов. По предположению [math]X_i \overset{*}{\underset{G}{\Rightarrow}}w_i[/math]. Теперь построим соответствующее порождение в [math]G[/math]. [math]A \underset {G}{\Rightarrow} Y_1 Y_2...Y_m \overset{*}{\underset{G}{\Rightarrow}} X_1 X_2...X_k \overset{*}{\underset{G}{\Rightarrow}} w_1 w_2...w_k = w[/math] Ч.т.д. [math]\Leftarrow[/math] Пусть [math]A \overset{*}{\underset{G}{\Rightarrow}}w[/math]  и  [math]w \ne \varepsilon[/math]. Докажем индукцией по длине порождения, что [math]A \overset{*}{\underset{G'}{\Rightarrow}}w[/math]. Обозначим длину порождения за [math]p[/math]. Базис. [math]p = 1[/math] [math]A \rightarrow w[/math] является правилом в [math]G[/math]. Поскольку [math]w \ne \varepsilon[/math], эта же правило будет и в [math]G'[/math], поэтому [math]A \overset{*}{\underset{G'}{\Rightarrow}}w[/math]. Предположение. Пусть [math][A \overset{*}{\underset{G}{\Rightarrow}}w[/math]  и  [math]w \ne \varepsilon] \Rightarrow [A \overset{*}{\underset{G'}{\Rightarrow}}w (A \ne S')][/math]  верно для [math]p \lt n[/math]. Переход. [math]p = n[/math] Пусть в порождении [math]n[/math] шагов, [math]n \gt 1[/math]. Тогда оно имеет вид [math]A\underset{G}{\Rightarrow}Y_1 Y_2...Y_m \overset{*}{\underset{G}{\Rightarrow}}w[/math], где [math]Y_i \in N \cup \Sigma [/math]. Цепочку [math]w[/math] можно разбить на [math]w_1 w_2...w_m[/math], где [math]Y_i \overset{*}{\underset{G'}{\Rightarrow}}w_i[/math]. Пусть [math]X_1, X_2, ... X_k[/math] будут теми из [math]Y_j[/math](в порядке записи), для которых [math]w_i \ne \varepsilon[/math]. [math]k \ge 1[/math], поскольку [math]w \ne \varepsilon[/math]. Таким образом [math]A \rightarrow X_1 X_2 ... X_k[/math] является правилом в [math]G'[/math] по построению [math]G'[/math]. Утверждаем, что [math] X_1 X_2...X_k \overset{*}{\underset{G}{\Rightarrow}}w[/math], поскольку только [math]Y_j[/math], которых нет среди [math]X_1, X_2, ... X_k[/math], использованы для порождения [math]\varepsilon[/math] и не вносят ничего в порождение [math]w[/math]. Так как каждое из порождений [math]Y_j \overset{*}{\underset{G}{\Rightarrow}}w_j[/math] содержит менее [math]n[/math] шагов, к ним можно применить предположение индукции и заключить, что если [math]w_j \ne \varepsilon[/math], то [math]Y_j \overset{*}{\underset{G'}{\Rightarrow}}w_j[/math]. Таким образом [math]A \underset{G'}{\rightarrow} X_1 X_2 ... X_k \overset{*}{\underset{G'}{\Rightarrow}} w[/math]. Ч.т.д.

[math]\triangleleft[/math]

Теперь можно доказать корректность:

Утверждение:

Алгоритм корректен: [math]L(G)=L(G')[/math]

[math]\triangleright[/math]

Подставив [math]S[/math] вместо [math]A[/math] в утверждении выше, видим, что [math]w \in L(G)[/math] для [math]w \ne \varepsilon[/math] тогда и только тогда, когда [math]w \in L(G')[/math]. Очевидно, что [math]\varepsilon \in L(G)[/math] тогда и только тогда, когда [math]\varepsilon \in L(G')[/math]. Таким образом, [math]L(G)=L(G')[/math].

[math]\triangleleft[/math]

Литература

• Ахо Альфред, Джеффри Ульман. Теория Синтаксического Анализа, Перевода и Компиляции. Том 1.
• Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.