Удаление eps-правил из грамматики — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Алгоритм удаления ε-правил из грамматики)
Строка 25: Строка 25:
 
<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> (*).
  
<tex>\Rightarrow)</tex><br\>
+
<tex>\Rightarrow</tex><br\>
 
Пусть <tex>A \underset{G'}{\Rightarrow}^*w</tex>&nbsp; и&nbsp; <tex>w \ne \varepsilon</tex>.<br/>
 
Пусть <tex>A \underset{G'}{\Rightarrow}^*w</tex>&nbsp; и&nbsp; <tex>w \ne \varepsilon</tex>.<br/>
 
Докажем индукцией по длине порождения в грамматике <tex>G'</tex>, что <tex>A \underset{G}{\Rightarrow}^*w</tex>.<br/>  
 
Докажем индукцией по длине порождения в грамматике <tex>G'</tex>, что <tex>A \underset{G}{\Rightarrow}^*w</tex>.<br/>  
Строка 35: Строка 35:
 
Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2...w_k</tex>, где <tex>X_i \underset{G'}{\Rightarrow}^*w_i</tex>. Если <tex>X_i</tex> — терминал, то <tex>w_i = X_i</tex>, a если нетерминал, то порождение <tex>X_i \underset{G'}{\Rightarrow}^*w_i</tex> содержит менее <tex>n</tex> шагов. По предположению <tex>X_i \underset{G}{\Rightarrow}^*w_i</tex>, значит <tex>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</tex>.
 
Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2...w_k</tex>, где <tex>X_i \underset{G'}{\Rightarrow}^*w_i</tex>. Если <tex>X_i</tex> — терминал, то <tex>w_i = X_i</tex>, a если нетерминал, то порождение <tex>X_i \underset{G'}{\Rightarrow}^*w_i</tex> содержит менее <tex>n</tex> шагов. По предположению <tex>X_i \underset{G}{\Rightarrow}^*w_i</tex>, значит <tex>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</tex>.
  
<tex>\Leftarrow)</tex><br/>
+
<tex>\Leftarrow</tex><br/>
 
Пусть <tex>A \underset{G}{\Rightarrow}^*w</tex>&nbsp; и&nbsp; <tex>w \ne \varepsilon</tex>.<br/>  
 
Пусть <tex>A \underset{G}{\Rightarrow}^*w</tex>&nbsp; и&nbsp; <tex>w \ne \varepsilon</tex>.<br/>  
 
Докажем индукцией по длине порождения в грамматике <tex>G</tex>, что <tex>A \underset{G'}{\Rightarrow}^*w</tex>.<br/>  
 
Докажем индукцией по длине порождения в грамматике <tex>G</tex>, что <tex>A \underset{G'}{\Rightarrow}^*w</tex>.<br/>  

Версия 16:18, 24 января 2012

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

Определение:
Правила вида [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].

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

Литература

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