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

Используемые определения

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

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

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

Нетерминал $A$ называется $\varepsilon$-порождающим, если $A \Rightarrow^* \varepsilon$.

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

Вход: КС грамматика $G=\langle N,\Sigma, P, S \rangle$.
Выход: КС грамматика $G'=\langle N,\Sigma, P', S' \rangle$ без $\varepsilon$-правил (может присутствовать правило $S \rightarrow \varepsilon$, но в этом случае $S$ не встречается в правых частях правил). $L(G') = L(G)$.

1. Добавить все правила из $P$ в $P'$.
2. Найти все $\varepsilon$-порождаюшие нетерминалы.
3. Рассмотрим правила вида (*) $A \rightarrow \alpha_0 B_1 \alpha_1 B_2 \alpha_2 ... B_k \alpha_k$, где $\alpha_i$ — последовательности из терминалов и нетерминалов, $B_j$ — $\varepsilon$-порождающие нетерминалы. Добавить все возможные правила вида (*) в $P'$, в которых либо присутствует, либо отсутствует $B_j\; (1 \le j \le k)$.
4. Удалить все $\varepsilon$-правила из $P'$.
5. Если в исходной грамматике $G$ выводилось $\varepsilon$, то необходимо добавить новый нетерминал $S'$, сделать его стартовым, добавить правила $S' \rightarrow S|\varepsilon$.

Доказательство корректности

Теорема:

Если грамматика $G'$ была построена с помощью описанного выше алгоритма по грамматике $G$, то $L(G') = L(G)$.

Доказательство:

$\triangleright$

Сначала докажем, что, если не выполнять шаг 5 алгоритма, то получится грамматика $G' : L(G') = L(G) \setminus \lbrace \varepsilon \rbrace$. Для этого достаточно доказать, что $A \underset{G'}{\Rightarrow}^*w$ тогда и только тогда, когда $A \underset{G}{\Rightarrow}^*w$ и $w \ne \varepsilon$ (*). $\Rightarrow)$<br\> Пусть $A \underset{G'}{\Rightarrow}^*w$  и  $w \ne \varepsilon$. Докажем индукцией по длине порождения в грамматике $G'$, что $A \underset{G}{\Rightarrow}^*w$. База. $A \underset{G'}{\Rightarrow} w$. В этом случае в $G'$ есть правило $A \rightarrow w$. По построению $G'$ в $G$ есть правило $A \rightarrow \alpha$, причем $\alpha$ — цепочка $w$, элементы которой, возможно, перемежаются $\varepsilon$-порождающими нетерминалами. Тогда в $G$ есть порождения $A \underset{G}{\Rightarrow} \alpha \underset{G}{\Rightarrow}^*w$. Предположение. Пусть из $A \underset{G'}{\Rightarrow}^*w \ne \varepsilon$ менее, чем за $n$ шагов, следует, что $A \underset{G}{\Rightarrow}^*w$. Переход. Пусть в порождении $n$ шагов, $n \gt 1$. Тогда оно имеет вид $A\underset{G'}{\Rightarrow}X_1 X_2...X_k \underset{G'}{\Rightarrow}^*w$, где $X_i \in N \cup \Sigma$. Первое использованное правило должно быть построено по правилу грамматики $G$ $A \rightarrow Y_1 Y_2...Y_m$, где последовательность $Y_1 Y_2...Y_m$ совпадает с последовательностью $X_1 X_2...X_k$, символы которой, возможно, перемежаются $\varepsilon$-порождающими нетерминалами. Цепочку $w$ можно разбить на $w_1 w_2...w_k$, где $X_i \underset{G'}{\Rightarrow}^*w_i$. Если $X_i$ — терминал, то $w_i = X_i$, a если нетерминал, то порождение $X_i \underset{G'}{\Rightarrow}^*w_i$ содержит менее $n$ шагов. По предположению $X_i \underset{G}{\Rightarrow}^*w_i$, значит $A \underset {G}{\Rightarrow} Y_1 Y_2...Y_m \underset{G}{\Rightarrow}^* X_1 X_2...X_k \underset{G}{\Rightarrow}^* w_1 w_2...w_k = w$. $\Leftarrow)$ Пусть $A \underset{G}{\Rightarrow}^*w$  и  $w \ne \varepsilon$. Докажем индукцией по длине порождения в грамматике $G$, что $A \underset{G'}{\Rightarrow}^*w$. База. $A \underset{G}{\Rightarrow} w$. Правило $A \rightarrow w$ присутствует в $G$. Поскольку $w \ne \varepsilon$, это же правило будет и в $G'$, поэтому $A \underset{G'}{\Rightarrow}^*w$. Предположение. Пусть из $A \underset{G}{\Rightarrow}^*w \ne \varepsilon$ менее, чем за $n$ шагов, следует, что $A \underset{G'}{\Rightarrow}^*w$. Переход. Пусть в порождении $n$ шагов, $n \gt 1$. Тогда оно имеет вид $A\underset{G}{\Rightarrow}Y_1 Y_2...Y_m \underset{G}{\Rightarrow}^*w$, где $Y_i \in N \cup \Sigma$. Цепочку $w$ можно разбить на $w_1 w_2...w_m$, где $Y_i \underset{G}{\Rightarrow}^*w_i$. Пусть $Y_{i_1}, Y_{i_2}, ..., Y_{i_p}$ — подпоследовательность, состоящая из всех элементов, таких, что $w_{i_k} \ne \varepsilon$, то есть $Y_{i_1} Y_{i_2} ... Y_{i_p} \underset{G}{\Rightarrow}^*w$. $p \ge 1$, поскольку $w \ne \varepsilon$. Значит, $A \rightarrow Y_{i_1} Y_{i_2} ... Y_{i_p}$ является правилом в $G'$ по построению $G'$. Так как каждое из порождений $Y_i \underset{G}{\Rightarrow}^*w_i$ содержит менее $n$ шагов, к ним можно применить предположение индукции и заключить, что, если $w_i \ne \varepsilon$, то $Y_i \underset{G'}{\Rightarrow}^*w_i$. Таким образом, $A \underset{G'}{\Rightarrow} Y_{i_1} Y_{i_2} ... Y_{i_p} \underset{G'}{\Rightarrow}^* w$. Подставив $S$ вместо $A$ в утверждение (*), видим, что $w \in L(G)$ для $w \ne \varepsilon$ тогда и только тогда, когда $w \in L(G')$. Так как после выполнения шага 5 алгоритма в $G'$ могло добавиться только пустое слово $\varepsilon$, то язык, задаваемый КС грамматикой $G'$, совпадает с языком, задаваемым КС грамматикой $G$.

$\triangleleft$

Алгоритм поиска ε-порождающих нетерминалов

Вход: КС грамматика $G=\langle N,\Sigma, P, S \rangle$.
Выход: множество $\varepsilon$-порождающих нетерминалов.

1. Найти все $\varepsilon$-правила. Составить множество, состоящее из нетерминалов, входящих в левые части таких правил.
2. Перебираем правила грамматики $G$. Если найдено правило $A \rightarrow C_1C_2...C_k$, для которого верно, что каждый $C_i$ принадлежит множеству, то добавить $A$ в множество.
3. Если на шаге 2 множество изменилось, то повторить шаг 2.

Теорема:

Описанный выше алгоритм находит все $\varepsilon$-порождающие нетерминалы грамматики $G$.

Доказательство:

$\triangleright$

Для доказательства корректности алгоритма достаточно показать, что, если множество $\varepsilon$-порождающих нетерминалов на очередной итерации алгоритма не изменялось, то алгоритм нашел все $\varepsilon$-порождающие нетерминалы. Пусть после завершения алгоритма существуют нетерминалы такие, что они являются $\varepsilon$-порождающими, но не были найдены алгоритмом. Выберем из этих нетерминалов нетерминал $B$, из которого выводится $\varepsilon$ за наименьшее число шагов. Тогда, в грамматике есть правило $B \rightarrow C_1C_2...C_k$, где каждый нетерминал $C_i$ — $\varepsilon$-порождающий. Каждый $C_i$ входит в множество $\varepsilon$-порождающих нетерминалов, так как иначе вместо $B$ необходимо было взять $C_i$. Следовательно, на одной из итераций алгоритма $B$ уже добавился в множество $\varepsilon$-порождающих нетерминалов. Противоречие. Следовательно, алгоритм находит все $\varepsilon$-порождающие нетерминалы.

$\triangleleft$

Литература

• Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — С. 273: ISBN 5-8459-0261-4 (рус.)