Удаление 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] \Gamma=\langle N,\Sigma, P, S \rangle[/math].
Выход: множество [math]\varepsilon[/math]-порождающих нетерминалов.

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

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

Теорема:

Описанный выше алгоритм находит все [math]\varepsilon[/math]-порождающие нетерминалы грамматики [math]\Gamma[/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]\mathtt{isEpsilon[nonterm_i]}[/math] — для каждого нетерминала будем хранить пометку, является он [math]\varepsilon[/math]-порождающим или нет.
• [math]\mathtt{concernedRules[nonterm_i]}[/math] — для каждого нетерминала будем хранить список номеров тех правил, в правой части которых он встречается;
• [math]\mathtt{counter[rule_i]}[/math] — для каждого правила будем хранить счетчик количества нетерминалов в правой части, которые еще не помечены [math]\varepsilon[/math]-порождающими;
• [math]\mathtt{Q}[/math] — очередь нетерминалов, помеченных [math]\varepsilon[/math]-порождающими, но еще не обработанных.

Сначала проставим [math]\mathtt{false}[/math] в [math]\mathtt{isEpsilon}[/math] для всех нетерминалов, а в [math]\mathtt{counter}[/math] для каждого правила запишем количество нетерминалов справа от него. Те правила, для которых [math]\mathtt{counter}[/math] сразу же оказался нулевым, добавим в [math]\mathtt{Q}[/math] и объявим истинным соответствующий [math]\mathtt{isEpsilon}[/math], так как это [math]\varepsilon[/math]-правила. Теперь будем доставать из очереди по одному нетерминалу, смотреть на список [math]\mathtt{concernedRules}[/math] для него и уменьшать [math]\mathtt{counter}[/math] для всех правил оттуда. Если [math]\mathtt{counter}[/math] какого-то правила в этот момент обнулился, то нетерминал из левой части этого правила помечается [math]\varepsilon[/math]-порождающим, если еще не был помечен до этого, и добавляется в [math]\mathtt{Q}[/math]. Продолжаем, пока очередь не станет пустой.

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

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

Пример

Рассмотрим грамматику, причем сразу пронумеруем правила:

1. [math]S\rightarrow ABC[/math]
2. [math]S\rightarrow DS [/math]
3. [math]A\rightarrow \varepsilon[/math]
4. [math]B\rightarrow AC[/math]
5. [math]C\rightarrow \varepsilon[/math]
6. [math]D\rightarrow d[/math]

Поскольку правило 6 содержит справа терминалы, оно заведомо не будет влиять на ответ, поэтому мы не будем его учитывать.

Построим массив списков [math]\mathtt{concernedRules}[/math].

[math]\mathtt{concernedRules}[/math]
[math]S[/math]	[math]A[/math]	[math]B[/math]	[math]C[/math]	[math]D[/math]
2	1, 4	1	1, 4	2

[math]\mathtt{Q}[/math]	[math]\mathtt{isEpsilon}[/math]					[math]\mathtt{counter}[/math]					Комментарий
[math]\left \{ \right \}[/math]	[math]S[/math]	[math]A[/math]	[math]B[/math]	[math]C[/math]	[math]D[/math]	1	2	3	4	5	Зададим начальные значения массивам [math]\mathtt{counter}[/math] и [math]\mathtt{isEpsilon}[/math].
	0	0	0	0	0	3	2	0	2	0
[math]\left \{A,C \right \}[/math]	[math]S[/math]	[math]A[/math]	[math]B[/math]	[math]C[/math]	[math]D[/math]	1	2	3	4	5	Заметим, что правила 3 и 5 являются [math]\varepsilon[/math]-правилами. Пометим левые нетерминалы из этих правил и добавим их в очередь. После этого в [math]\mathtt{Q}[/math] лежит [math]A[/math] и [math]C[/math], а [math]\mathtt{counter}[/math] остался без изменений.
	0	1	0	1	0	3	2	0	2	0
[math]\left\{C \right\}[/math]	[math]S[/math]	[math]A[/math]	[math]B[/math]	[math]C[/math]	[math]D[/math]	1	2	3	4	5	Достанем из очереди [math]A[/math], декрементируем те счетчики, которые относятся к связанным с ним правилам. К очереди ничего не добавится.
	0	1	0	1	0	2	2	0	1	0
[math]\left\{B \right\}[/math]	[math]S[/math]	[math]A[/math]	[math]B[/math]	[math]C[/math]	[math]D[/math]	1	2	3	4	5	Достанем из очереди [math]C[/math]. После проведения действий из алгоритма в очередь добавится [math]B[/math].
	0	1	1	1	0	1	2	0	0	0
[math]\left\{S \right\}[/math]	[math]S[/math]	[math]A[/math]	[math]B[/math]	[math]C[/math]	[math]D[/math]	1	2	3	4	5	Достанем из очереди [math]B[/math]. После действий алгоритма в очередь добавится [math]S[/math].
	1	1	1	1	0	0	2	0	0	0
[math]\left\{ \right\}[/math]	[math]S[/math]	[math]A[/math]	[math]B[/math]	[math]C[/math]	[math]D[/math]	1	2	3	4	5	Достанем из очереди [math]S[/math]. Ничего не добавится в очередь и она останется пустой. Алгоритм закончил свое выполнение. Итого в множество [math]\varepsilon[/math]-правил входят все нетерминалы, кроме [math]D[/math].
	1	1	1	1	0	0	1	0	0	0

Если применять алгоритм без модификации с очередью, то действия будут следующие:

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].

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

Вход: КС-грамматика [math] \Gamma=\langle N,\Sigma, P, S \rangle[/math].
Выход: КС-грамматика [math] \Gamma'=\langle N,\Sigma, P', S' \rangle[/math] без [math]\varepsilon[/math]-правил (может присутствовать правило [math]S \rightarrow \varepsilon[/math], но в этом случае [math]S[/math] не встречается в правых частях правил); [math]L(\Gamma') = L(\Gamma)[/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 \leqslant j \leqslant k)[/math].
4. Удалить все [math]\varepsilon[/math]-правила из [math]P'[/math].
5. Если в исходной грамматике [math]\Gamma[/math] выводилось [math]\varepsilon[/math], то необходимо добавить новый нетерминал [math]S'[/math], сделать его стартовым, добавить правило [math]S' \rightarrow S|\varepsilon[/math].

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

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

Рассмотрим грамматику [math]\Gamma[/math]:

[math]S\rightarrow T_1 T_2 T_3 \ldots T_n[/math]

[math]T_1\rightarrow t_1|\varepsilon[/math]

[math]T_2\rightarrow t_2|\varepsilon[/math]

[math]\ldots\[/math]

[math]T_n\rightarrow t_n|\varepsilon[/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]\left| \Gamma \right| = O(n)[/math]. Однако алгоритм удаления [math]\varepsilon[/math]-правил будет работать за [math]O(\left| \Gamma \right|)[/math], поскольку для каждого правила можно будет добавить только [math]O(1)[/math] сочетаний нетерминалов.

Пример

Рассмотрим грамматику:

[math]S\rightarrow ABCd[/math]

[math]A\rightarrow a|\varepsilon[/math]

[math]B\rightarrow AC[/math]

[math]C\rightarrow c|\varepsilon[/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]S\rightarrow Ad|ABd|ACd|ABCd|Bd|BCd|Cd|d[/math]

[math]A\rightarrow a[/math]

[math]B\rightarrow A|AC|C[/math]

[math]C\rightarrow c[/math]

См. также

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

Источники информации

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