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

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

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

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

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

Нетерминал [math]A[/math] называется [math]\varepsilon[/math]-порождающим ([math]\varepsilon[/math]-generating), если [math]A \Rightarrow^* \varepsilon[/math].

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

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

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

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

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Время работы алгоритма

Рассмотрим грамматику: [math] \Gamma = \begin{array}{l l} S\rightarrow T_1 T_2 T_3 ... T_n\\ T_1\rightarrow t_1|\varepsilon\\ T_2\rightarrow t_2|\varepsilon\\ ...\\ T_n\rightarrow t_n|\varepsilon \end{array} [/math].
[math]\left| \Gamma \right| = O(n)[/math]. Из нетерминала [math]S[/math] можно вывести [math]2^n[/math] сочетаний нетерминалов [math]T_i[/math]. Таким образом в худшем случае алгоритм работает за [math]O(2^{\left| \Gamma \right|})[/math].
Однако если в грамматике устранены длинные правила, то алгоритм будет работать за [math]O(\left| \Gamma \right|)[/math] и добавит в грамматику [math]O(\left| \Gamma \right|)[/math] новых правил длинны [math]O(1)[/math].

Пример

Рассмотрим грамматику: [math] \begin{array}{l l} S\rightarrow ABCd\\ A\rightarrow a|\varepsilon\\ B\rightarrow AC\\ C\rightarrow c|\varepsilon \end{array} [/math], в которой [math]A[/math], [math]B[/math] и [math]C[/math] являются [math]\varepsilon[/math]-порождающими нетерминалами.

1. Переберём для каждого правила все возможные сочетания ε-порождающих нетерминалов и добавим новые правила:
   • [math]S\rightarrow Ad|ABd|ACd|Bd|BCd|Cd|d[/math] для [math]S \rightarrow ABCd[/math]
   • [math]B \rightarrow A|C[/math] для [math]B \rightarrow AC[/math]
2. Удалим праила [math]A\rightarrow \varepsilon[/math] и [math]C\rightarrow \varepsilon[/math]

В результате мы получим новую грамматику без [math]\varepsilon[/math]-правил: [math]\begin{array}{l l} S\rightarrow Ad|ABd|ACd|ABCd|Bd|BCd|Cd|d\\ A\rightarrow a\\ B\rightarrow A|AC|C\\ C\rightarrow c \end{array}[/math]

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

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

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

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

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Время работы алгоритма

Данный алгоритм работает за [math]O(\left| \Gamma \right| ^ 2)[/math], однако используя очередь можно ускорить его до [math]O(\left| \Gamma \right|)[/math].

Пример

Рассмотрим грамматику: [math] \begin{array}{l l} S\rightarrow ABC|DS\\ A\rightarrow \varepsilon\\ B\rightarrow AC\\ C\rightarrow \varepsilon\\ D\rightarrow d \end{array} [/math]

1. Возьмём множество состоящее из [math]\varepsilon[/math]-порождающих нетерминалов [math]\lbrace A, C \rbrace[/math].
2. Добавим [math]B[/math] в множество, так как правая часть правила [math]B\rightarrow AC[/math] состоит только из нетерминалов из множества.
3. Повторим второй пункт для правила [math]S\rightarrow ABC[/math] и получим множество [math]\lbrace A, B, C, S \rbrace[/math].
4. Больше нет нерассмотренных правил, содержащих справа только нетерминалы из множества.

Таким образом [math]\varepsilon[/math]-порождающими нетерминалами являются [math]A[/math], [math]B[/math], [math]C[/math] и [math]S[/math].

См. также

• Контекстно-свободные грамматики
• Нормальная форма Хомского
• Chomsky normal form

Литература

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