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

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

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

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

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

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

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

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

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

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

Вход. КС грамматика $G=\langle N,\Sigma, P, S \rangle$.

Выход. Множество $\varepsilon$-порождающих нетерминалов.

Схема алгоритма:

1. Если $A \rightarrow \varepsilon$ — правило грамматики $G$, то $A$ — $\varepsilon$-порождающий нетерминал.
2. Если $B \rightarrow C_1C_2...C_k$ — правило грамматики $G$, где каждый $C_i$ — $\varepsilon$-порождающий нетерминал, то $B$ — $\varepsilon$-порождающий нетерминал.

Теорема:

Нетерминал $A$ является $\varepsilon$-порождающим тогда и только тогда, когда вышеприведенный алгоритм идентифицирует $A$ как $\varepsilon$-порождающий.

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

$\triangleright$

Индукция по длине кратчайшего порождения $A \Rightarrow^* \varepsilon$ База. $A \Rightarrow^* \varepsilon$ за один шаг, то есть $A \rightarrow\varepsilon$. $\varepsilon$-порождающий нетерминал $A$ обнаруживается алгоритмом согласно первому пункту алгоритма. Индукция. Пусть $A \Rightarrow^* \varepsilon$ за $n$ шагов. Тогда первых шаг порождения $A \rightarrow C_1C_2...C_k$, где $C_i \Rightarrow^* \varepsilon$ за менее, чем $n$ шагов. По индукционному предположению каждый нетерминал $C_i$ обнаруживается как $\varepsilon$-порождающий. Тогда нетерминал $A$ обнаружиться вторым пунктом алгоритма как $\varepsilon$-порождающий.

$\triangleleft$

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

Вход. КС грамматика $G=\langle N,\Sigma, P, S \rangle$.

Выход. КС грамматика $G'=\langle N,\Sigma, P', S \rangle : L(G) \setminus \mathcal {f} \varepsilon \mathcal {g} = L(G')$.

Схема алгоритма:

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

Замечание

Если в исходной грамматике $G$ есть правило $S \rightarrow \varepsilon$ и $S$ встречается в правых частях, то для того, чтобы получить эквивалентную грамматику без $\varepsilon$-правил, необходимо после применения описанного выше алгоритма добавить новый нетерминал $S'$, сделать его стартовым, добавить правила $S' \rightarrow S|\varepsilon$.

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

Теорема:

Если грамматика $G'$ была построена с помощью описанного выше алгоритма по грамматике $G$, то $L(G') = L(G) \setminus \mathcal {f}\varepsilon \mathcal {g}$.

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

$\triangleright$

Для этого достаточно доказать, что $A \underset{G'}{\Rightarrow}^*w$ тогда и только тогда, когда $A \underset{G}{\Rightarrow}^*w$ и $w \ne \varepsilon$ (*). $\Rightarrow)$<br\> Пусть $A \underset{G'}{\Rightarrow}^*w$. Несомненно, $w \ne \varepsilon$, поскольку $G'$ - грамматика без $\varepsilon$-правил. Докажем индукцией по длине порождения, что $A \underset{G}{\Rightarrow}^*w$. Обозначим длину порождения за $p$. Базис. $p = 1$ В этом случае в $G'$ есть правило $A \rightarrow w$. Согласно конструкции $G'$ в $G$ есть правило $A \rightarrow \alpha$, причем $\alpha-$ это $w$, символы которой, возможно, перемежаются $\varepsilon-$ порождающими нетерминалами. Тогда в $G$ есть порождения $A \underset{G}{\Rightarrow} \alpha \underset{G}{\Rightarrow}^*w$, где на шагах после первого, из всех нетерминалов в цепочке $\alpha$ выводиться $\varepsilon$. Предположение. Пусть из $A \underset{G'}{\Rightarrow}^*w$ следует, что $A \underset{G}{\Rightarrow}^*w$ и $w \ne \varepsilon$ верно для $p \lt n$. Переход. $p = n$ Пусть в порождении $n$ шагов, $n \gt 1$. Тогда оно имеет вид $A\underset{G'}{\Rightarrow}X_1 X_2...X_k \underset{G'}{\Rightarrow}w^*$, где $X_i \in N \cup \Sigma$. Первое использованное правило должно быть построено по правилу $A \rightarrow Y_1 Y_2...Y_m$, где цепочка $Y_1 Y_2...Y_m$ совпадает с цепочкой $X_1 X_2...X_k$, цепочка $Y_1 Y_2...Y_m$, возможно, перемежаются $\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$. Теперь построим соответствующее порождение в $G$. $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$. Докажем индукцией по длине порождения, что $A \underset{G'}{\Rightarrow}^*w$. Обозначим длину порождения за $p$. Базис. $p = 1$ $A \rightarrow w$ является правилом в $G$. Поскольку $w \ne \varepsilon$, это же правило будет и в $G'$, поэтому $A \underset{G'}{\Rightarrow}^*w$. Предположение. Пусть из $A \underset{G}{\Rightarrow}^*w$ и $w \ne \varepsilon следует, что A \underset{G'}{\Rightarrow}^*w$ верно для $p \lt n$. Переход. $p = n$ Пусть в порождении $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$. Пусть $X_1, X_2, ... X_k$ будут теми из $Y_j$ (в порядке записи), для которых $w_i \ne \varepsilon$. $k \ge 1$, поскольку $w \ne \varepsilon$. Таким образом $A \rightarrow X_1 X_2 ... X_k$ является правилом в $G'$ по построению $G'$. Утверждаем, что $X_1 X_2...X_k \underset{G}{\Rightarrow}^*w$, поскольку только $Y_j$, которых нет среди $X_1, X_2, ... X_k$, использованы для порождения $\varepsilon$ и не вносят ничего в порождение $w$. Так как каждое из порождений $Y_j \underset{G}{\Rightarrow}^*w_j$ содержит менее $n$ шагов, к ним можно применить предположение индукции и заключить, что если $w_j \ne \varepsilon$, то $Y_j \underset{G'}{\Rightarrow}^*w_j$. Таким образом $A \underset{G'}{\rightarrow} X_1 X_2 ... X_k \underset{G'}{\Rightarrow}^* w$. Ч.т.д. Подставив $S$ вместо $A$ в утверждение (*), видим, что $w \in L(G)$ для $w \ne \varepsilon$ тогда и только тогда, когда $w \in L(G')$.

$\triangleleft$

Литература

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