Используемые определения
| Определение: |
| Правила вида [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]-порождающих нетерминалов.
- Найти все [math]\varepsilon[/math]-правила. Составить множество, состоящее из нетерминалов, входящих в левые части таких правил.
- Перебираем правила грамматики [math]\Gamma[/math]. Если найдено правило [math]A \rightarrow C_1C_2...C_k[/math], для которого верно, что каждый [math]C_i[/math] принадлежит множеству, то добавить [math]A[/math] в множество.
- Если на шаге 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].
Пример
Рассмотрим грамматику, причем сразу пронумеруем правила:
- [math]S\rightarrow ABC[/math]
- [math]S\rightarrow DS [/math]
- [math]A\rightarrow \varepsilon[/math]
- [math]B\rightarrow AC[/math]
- [math]C\rightarrow \varepsilon[/math]
- [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
|
Если применять алгоритм без модификации с очередью, то действия будут следующие:
- Возьмём множество состоящее из [math]\varepsilon[/math]-порождающих нетерминалов [math]\lbrace A, C \rbrace[/math].
- Добавим [math]B[/math] в множество, так как правая часть правила [math]B\rightarrow AC[/math] состоит только из нетерминалов из множества.
- Повторим второй пункт для правила [math]S\rightarrow ABC[/math] и получим множество [math]\lbrace A, B, C, S \rbrace[/math].
- Больше нет нерассмотренных правил, содержащих справа только нетерминалы из множества.
Таким образом [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].
- Добавить все правила из [math]P[/math] в [math]P'[/math].
- Найти все [math]\varepsilon[/math]-порождаюшие нетерминалы.
- Для каждого правила вида [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].
- Удалить все [math]\varepsilon[/math]-правила из [math]P'[/math].
- Если в исходной грамматике [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]
Пусть [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]-порождающими нетерминалами.
- Переберём для каждого правила все возможные сочетания ε-порождающих нетерминалов и добавим новые правила:
- [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]
- Удалим праила [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
