|
|
| Строка 21: |
Строка 21: |
| | |statement = Если грамматика <tex>G'</tex> была построена с помощью описанного выше алгоритма по грамматике <tex>G</tex>, то <tex>L(G') = L(G)</tex>. | | |statement = Если грамматика <tex>G'</tex> была построена с помощью описанного выше алгоритма по грамматике <tex>G</tex>, то <tex>L(G') = L(G)</tex>. |
| | |proof = | | |proof = |
| − | Сначала докажем, что если не выполнять шаг 5 алгоритма, то получится грамматика <tex>G' : L(G') = L(G) \setminus \lbrace \varepsilon \rbrace </tex>.<br/> | + | Сначала докажем, что, если не выполнять шаг 5 алгоритма, то получится грамматика <tex>G' : L(G') = L(G) \setminus \lbrace \varepsilon \rbrace </tex>.<br/> |
| | Для этого достаточно доказать, что | | Для этого достаточно доказать, что |
| | <tex>A \underset{G'}{\Rightarrow}^*w</tex> тогда и только тогда, когда <tex>A \underset{G}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex> (*). | | <tex>A \underset{G'}{\Rightarrow}^*w</tex> тогда и только тогда, когда <tex>A \underset{G}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex> (*). |
| Строка 28: |
Строка 28: |
| | Пусть <tex>A \underset{G'}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex>.<br/> | | Пусть <tex>A \underset{G'}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex>.<br/> |
| | Докажем индукцией по длине порождения, что <tex>A \underset{G}{\Rightarrow}^*w</tex>.<br/> | | Докажем индукцией по длине порождения, что <tex>A \underset{G}{\Rightarrow}^*w</tex>.<br/> |
| − | '''База'''. Пусть <tex>A \underset{G'}{\Rightarrow}^*w</tex>.<br/> | + | '''База'''. <tex>A \underset{G'}{\Rightarrow} w</tex>.<br/> |
| − | В этом случае в <tex>G'</tex> есть правило <tex>A \rightarrow w</tex>. Согласно конструкции <tex>G'</tex> в <tex>G</tex> есть правило <tex>A \rightarrow \alpha</tex>, причем <tex>\alpha</tex> — цепочка <tex>w</tex>, символы которой, возможно, перемежаются <tex>\varepsilon</tex>-порождающими нетерминалами. Тогда в <tex>G</tex> есть порождения <tex>A \underset{G}{\Rightarrow} \alpha \underset{G}{\Rightarrow}w</tex>.<br/> | + | В этом случае в <tex>G'</tex> есть правило <tex>A \rightarrow w</tex>. По построению <tex>G'</tex> в <tex>G</tex> есть правило <tex>A \rightarrow \alpha</tex>, причем <tex>\alpha</tex> — цепочка <tex>w</tex>, символы которой, возможно, перемежаются <tex>\varepsilon</tex>-порождающими нетерминалами. Тогда в <tex>G</tex> есть порождения <tex>A \underset{G}{\Rightarrow} \alpha \underset{G}{\Rightarrow}w</tex>.<br/> |
| − | '''Предположение'''. Пусть из <tex>A \underset{G'}{\Rightarrow}^*w</tex> следует, что <tex>A \underset{G}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex> менее, чем за <tex>n</tex> шагов.<br/> | + | '''Предположение'''. Пусть из <tex>A \underset{G'}{\Rightarrow}^*w \ne \varepsilon</tex> следует, что <tex>A \underset{G}{\Rightarrow}^*w</tex> менее, чем за <tex>n</tex> шагов.<br/> |
| | '''Переход'''. | | '''Переход'''. |
| | Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G'}{\Rightarrow}X_1 X_2...X_k | | Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G'}{\Rightarrow}X_1 X_2...X_k |
| Строка 41: |
Строка 41: |
| | Пусть <tex>A \underset{G}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex>.<br/> | | Пусть <tex>A \underset{G}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex>.<br/> |
| | Докажем индукцией по длине порождения, что <tex>A \underset{G'}{\Rightarrow}^*w</tex>.<br/> | | Докажем индукцией по длине порождения, что <tex>A \underset{G'}{\Rightarrow}^*w</tex>.<br/> |
| − | '''База'''. Пусть <tex>A \underset{G}{\Rightarrow}^*w</tex>.<br/> | + | '''База'''. <tex>A \underset{G}{\Rightarrow} w</tex>.<br/> |
| − | <tex>A \rightarrow w</tex> является правилом в <tex>G</tex>. Поскольку <tex>w \ne \varepsilon</tex>, это же правило будет и в <tex>G'</tex>, поэтому <tex>A \underset{G'}{\Rightarrow}^*w</tex>.<br/> | + | Правило <tex>A \rightarrow w</tex> присутствует в <tex>G</tex>. Поскольку <tex>w \ne \varepsilon</tex>, это же правило будет и в <tex>G'</tex>, поэтому <tex>A \underset{G'}{\Rightarrow}^*w</tex>.<br/> |
| | '''Предположение'''. Пусть из <tex>A \underset{G}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex> следует, что <tex>A \underset{G'}{\Rightarrow}^*w </tex> менее, чем за <tex>n</tex> шагов.<br/> | | '''Предположение'''. Пусть из <tex>A \underset{G}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex> следует, что <tex>A \underset{G'}{\Rightarrow}^*w </tex> менее, чем за <tex>n</tex> шагов.<br/> |
| | '''Переход'''. Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G}{\Rightarrow}Y_1 Y_2...Y_m | | '''Переход'''. Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G}{\Rightarrow}Y_1 Y_2...Y_m |
Используемые определения
| Определение: |
| Правила вида [math]A \to \varepsilon[/math] называются [math]\varepsilon[/math]-правилами. |
| Определение: |
| Нетерминал [math]A[/math] называется [math]\varepsilon[/math]-порождающим, если [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].
- Добавить все правила из [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 \le j \le k)[/math].
- Удалить все [math]\varepsilon[/math]-правила из [math]P'[/math].
- Если в исходной грамматике [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]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]A \underset{G}{\Rightarrow}^*w[/math] менее, чем за [math]n[/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]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]Y_1 Y_2...Y_m[/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]G[/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]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[/math] и [math]w \ne \varepsilon[/math] следует, что [math]A \underset{G'}{\Rightarrow}^*w [/math] менее, чем за [math]n[/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]X_1, X_2, ... X_k[/math] будут теми из [math]Y_j[/math] (в порядке записи), для которых [math]w_i \ne \varepsilon[/math]. [math]k \ge 1[/math], поскольку [math]w \ne \varepsilon[/math].
Таким образом [math]A \rightarrow X_1 X_2 ... X_k[/math] является правилом в [math]G'[/math] по построению [math]G'[/math].
Утверждаем, что [math] X_1 X_2...X_k \underset{G}{\Rightarrow}^*w[/math], поскольку только [math]Y_j[/math], которых нет среди [math]X_1, X_2, ... X_k[/math], использованы для порождения [math]\varepsilon[/math] и не вносят ничего в порождение [math]w[/math].
Так как каждое из порождений [math]Y_j \underset{G}{\Rightarrow}^*w_j[/math] содержит менее [math]n[/math] шагов, к ним можно применить предположение индукции и заключить, что если [math]w_j \ne \varepsilon[/math], то [math]Y_j \underset{G'}{\Rightarrow}^*w_j[/math].
Таким образом [math]A \underset{G'}{\rightarrow} X_1 X_2 ... X_k \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] G=\langle N,\Sigma, P, S \rangle[/math].
Выход: множество [math]\varepsilon[/math]-порождающих нетерминалов.
- Найти все [math]\varepsilon[/math]-правила. Составить множество, состоящее из нетерминалов, входящих в левые части таких правил.
- Если существует правило [math]A \rightarrow C_1C_2...C_k[/math], для которого верно, что каждый [math]C_i[/math] принадлежит множеству, то добавить [math]A[/math] в множество.
- Если на шаге 2 множество изменилось, то повторить шаг 2.
| Теорема: |
Описанный выше алгоритм находит все [math]\varepsilon[/math]-порождающие нетерминалы грамматики [math]G[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Индукция по длине кратчайшего порождения [math]A \Rightarrow^* \varepsilon[/math]. Если длина кратчайшего порождения равна [math]p[/math], то в множестве [math]\varepsilon[/math]-порождающих нетерминалов содержатся все нетерминалы, из которых можно вывести пустое слово [math]\varepsilon[/math] за менее, чем [math]p[/math] шагов.
База. [math]A \Rightarrow \varepsilon[/math], то есть в грамматике имеется правило [math]A \rightarrow\varepsilon[/math]. Следовательно, [math]A[/math] будет добавлен в множество [math]\varepsilon[/math]-порождающих нетерминалов на первом шаге алгоритма.
Переход. Пусть [math]A \Rightarrow^* \varepsilon[/math] за [math]n[/math] шагов. Тогда первый шаг порождения выполняется по правилу [math]A \rightarrow C_1C_2...C_k[/math], где [math]C_i \Rightarrow^* \varepsilon[/math] за менее, чем [math]n[/math] шагов. По индукционному предположению каждый нетерминал [math]C_i[/math] уже содержится в множестве [math]\varepsilon[/math]-порождающих нетерминалов. Тогда нетерминал [math]A[/math] будет добавлен в множество [math]\varepsilon[/math]-порождающих нетерминалов на шаге 2. Следовательно, алгоритм находит все [math]\varepsilon[/math]-порождающие нетерминалы. |
| [math]\triangleleft[/math] |
Литература
- Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — С. 273: ISBN 5-8459-0261-4 (рус.)
