Удаление 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]

Литература

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