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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Схема алгоритма удаления ε-правил из грамматики)
(Доказательство корректности алгоритма)
Строка 49: Строка 49:
  
 
<tex>\Rightarrow)</tex><br\>
 
<tex>\Rightarrow)</tex><br\>
Пусть <tex>A \overset{*}{\underset{G'}{\Rightarrow}}w</tex>. Несомненно, <tex>w \ne \varepsilon</tex>, поскольку <tex>G'</tex> - грамматика без <tex>\varepsilon</tex>-правил и <tex>A \ne S'</tex>.<br/>Докажем индукцией по длине порождения, что <tex>A \overset{*}{\underset{G}{\Rightarrow}}w</tex>.<br/>  
+
Пусть <tex>A \overset{*}{\underset{G'}{\Rightarrow}}w</tex>. Несомненно, <tex>w \ne \varepsilon</tex>, поскольку <tex>G'</tex> - грамматика без <tex>\varepsilon</tex>-правил.<br/>Докажем индукцией по длине порождения, что <tex>A \overset{*}{\underset{G}{\Rightarrow}}w</tex>.<br/>  
 
Обозначим длину порождения за <tex>p</tex>.
 
Обозначим длину порождения за <tex>p</tex>.
 
:'''Базис'''. <tex>p = 1</tex><br/>
 
:'''Базис'''. <tex>p = 1</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 \overset{*}{\underset{G}{\Rightarrow}}w</tex>, где на шагах после первого, из всех переменных в цепочке <tex>\alpha</tex> выводиться <tex>\varepsilon</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 \overset{*}{\underset{G}{\Rightarrow}}w</tex>, где на шагах после первого, из всех нетерминалов в цепочке <tex>\alpha</tex> выводиться <tex>\varepsilon</tex>.<br/>
 
:'''Предположение'''. Пусть из <tex>A \overset{*}{\underset{G'}{\Rightarrow}}w</tex> следует, что <tex>A \overset{*}{\underset{G}{\Rightarrow}}w</tex> и <tex>w \ne \varepsilon</tex> верно для <tex>p < n</tex>.<br/>
 
:'''Предположение'''. Пусть из <tex>A \overset{*}{\underset{G'}{\Rightarrow}}w</tex> следует, что <tex>A \overset{*}{\underset{G}{\Rightarrow}}w</tex> и <tex>w \ne \varepsilon</tex> верно для <tex>p < n</tex>.<br/>
 
:'''Переход'''. <tex>p = n</tex><br/>
 
:'''Переход'''. <tex>p = 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
\overset{*}{\underset{G'}{\Rightarrow}}w</tex>, где <tex>X_i \in N \cup \Sigma </tex>. Первое использованное правило должно быть построено по правилу <tex>A \rightarrow Y_1 Y_2...Y_m</tex>, где цепочка <tex>Y_1 Y_2...Y_m</tex> совпадает с цепочкой <tex>X_1 X_2...X_k</tex>, цепочка <tex>Y_1 Y_2...Y_m</tex>, возможно, перемежаются <tex>\varepsilon-</tex> порождающими переменными.<br/>
+
\overset{*}{\underset{G'}{\Rightarrow}}w</tex>, где <tex>X_i \in N \cup \Sigma </tex>. Первое использованное правило должно быть построено по правилу <tex>A \rightarrow Y_1 Y_2...Y_m</tex>, где цепочка <tex>Y_1 Y_2...Y_m</tex> совпадает с цепочкой <tex>X_1 X_2...X_k</tex>, цепочка <tex>Y_1 Y_2...Y_m</tex>, возможно, перемежаются <tex>\varepsilon-</tex> порождающими нетерминалами.<br/>
Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2...w_k</tex>, где <tex>X_i \overset{*}{\underset{G'}{\Rightarrow}}w_i</tex>. Если <tex>X_i</tex> есть терминал, то <tex>w = X_i</tex>, a если переменная, то порождение <tex>X_i \overset{*}{\underset{G'}{\Rightarrow}}w_i</tex> содержит менее <tex>n</tex> шагов.<br/> По предположению <tex>X_i \overset{*}{\underset{G}{\Rightarrow}}w_i</tex>.<br/>
+
Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2...w_k</tex>, где <tex>X_i \overset{*}{\underset{G'}{\Rightarrow}}w_i</tex>. Если <tex>X_i</tex> есть терминал, то <tex>w = X_i</tex>, a если нетерминал, то порождение <tex>X_i \overset{*}{\underset{G'}{\Rightarrow}}w_i</tex> содержит менее <tex>n</tex> шагов.<br/> По предположению <tex>X_i \overset{*}{\underset{G}{\Rightarrow}}w_i</tex>.<br/>
 
Теперь построим соответствующее порождение в <tex>G</tex>.<br/>
 
Теперь построим соответствующее порождение в <tex>G</tex>.<br/>
 
:<tex>A \underset {G}{\Rightarrow} Y_1 Y_2...Y_m \overset{*}{\underset{G}{\Rightarrow}} X_1 X_2...X_k \overset{*}{\underset{G}{\Rightarrow}} w_1 w_2...w_k = w</tex><br/>
 
:<tex>A \underset {G}{\Rightarrow} Y_1 Y_2...Y_m \overset{*}{\underset{G}{\Rightarrow}} X_1 X_2...X_k \overset{*}{\underset{G}{\Rightarrow}} w_1 w_2...w_k = w</tex><br/>

Версия 19:23, 16 ноября 2011

Основные определения

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


Определение:
Назовем КС грамматику [math]G=(N,\Sigma, P, S)[/math] грамматикой без [math]\varepsilon[/math]-правил (или неукорачивающей), если либо
(1) [math]P[/math] не содержит [math]\varepsilon[/math]-правил, либо
(2) есть точно одно [math]\varepsilon[/math]-правило [math]S \to \varepsilon[/math] и [math]S[/math] не встречается в правых частях остальных правил из [math]P[/math].


Определение:
Нетерминал [math]A[/math] называется [math]\varepsilon[/math]-порождающим, если [math]A \overset{*}{\Rightarrow} \varepsilon[/math].


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

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

Схема алгоритма:

1) Если [math]A \rightarrow \varepsilon[/math] — правило грамматики [math]G[/math], то [math]A[/math][math]\varepsilon[/math]-порождающий нетерминал.
2) Если [math]B \rightarrow C_1C_2...C_k[/math] — правило грамматики [math]G[/math], где каждый [math]C_i[/math][math]\varepsilon[/math]-порождающий нетерминал, то [math]B[/math][math]\varepsilon[/math]-порождающий нетерминал.
Теорема:
Нетерминал [math]A[/math] является [math]\varepsilon[/math]-порождающим тогда и только тогда, когда вышеприведенный алгоритм идентифицирует [math]A[/math] как [math]\varepsilon[/math]-порождающий.
Доказательство:
[math]\triangleright[/math]

Индукция по длине кратчайшего порождения [math]A \overset{*}{\Rightarrow} \varepsilon[/math]

База. [math]A \overset{*}{\Rightarrow} \varepsilon[/math] за один шаг, то есть [math]A \rightarrow\varepsilon[/math]. [math]\varepsilon[/math]-порождающий нетерминал [math]A[/math] обнаруживается алгоритмом согласно первому пункту алгоритма.
Индукция. Пусть [math]A \overset{*}{\Rightarrow} \varepsilon[/math] за [math]n[/math] шагов. Тогда первых шаг порождения [math]A \rightarrow C_1C_2...C_k[/math], где [math]C_i \overset{*}{\Rightarrow} \varepsilon[/math] за менее, чем [math]n[/math] шагов. По индукционному предположению каждый нетерминал [math]C_i[/math] обнаруживается как [math]\varepsilon[/math]-порождающий. Тогда нетерминал [math]A[/math] обнаружиться вторым пунктом алгоритма как [math]\varepsilon[/math]-порождающий.
[math]\triangleleft[/math]

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

Вход. КС грамматика [math] G=(N,\Sigma, P, S)[/math].

Выход. КС грамматика [math] G'=(N,\Sigma, P', S) : L(G) - {\varepsilon} = L(G')[/math].

Схема алгоритма:

1) Найти все [math]\varepsilon[/math]-порождаюшие нетерминалы.
2) Удалить все [math]\varepsilon[/math]-правила из [math]P[/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]B_j\; (1 \le j \le k)[/math], кроме правила [math]A \rightarrow \varepsilon[/math]. Такое правило может возникнуть, если все [math]\alpha_i = \varepsilon[/math].

Замечание

Если в исходной грамматике [math]G[/math] есть правило [math]S \rightarrow \varepsilon[/math] и [math]S[/math] встречается в правых частях, то для того, чтобы получить эквивалентную грамматику без [math]\varepsilon[/math]-правил, необходимо после применения описанного выше алгоритма добавить новый нетерминал [math]S'[/math], сделать его стартовым, добавить правила [math]S' \rightarrow S|\varepsilon[/math].

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

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

Для этого достаточно доказать, что [math]A \overset{*}{\underset{G'}{\Rightarrow}}w[/math] тогда и только тогда, когда [math]A \overset{*}{\underset{G}{\Rightarrow}}w[/math] и [math]w \ne \varepsilon[/math] (*).

[math]\Rightarrow)[/math]<br\> Пусть [math]A \overset{*}{\underset{G'}{\Rightarrow}}w[/math]. Несомненно, [math]w \ne \varepsilon[/math], поскольку [math]G'[/math] - грамматика без [math]\varepsilon[/math]-правил.
Докажем индукцией по длине порождения, что [math]A \overset{*}{\underset{G}{\Rightarrow}}w[/math].
Обозначим длину порождения за [math]p[/math].

Базис. [math]p = 1[/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 \overset{*}{\underset{G}{\Rightarrow}}w[/math], где на шагах после первого, из всех нетерминалов в цепочке [math]\alpha[/math] выводиться [math]\varepsilon[/math].

Предположение. Пусть из [math]A \overset{*}{\underset{G'}{\Rightarrow}}w[/math] следует, что [math]A \overset{*}{\underset{G}{\Rightarrow}}w[/math] и [math]w \ne \varepsilon[/math] верно для [math]p \lt n[/math].
Переход. [math]p = n[/math]

Пусть в порождении [math]n[/math] шагов, [math]n \gt 1[/math]. Тогда оно имеет вид [math]A\underset{G'}{\Rightarrow}X_1 X_2...X_k \overset{*}{\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 \overset{*}{\underset{G'}{\Rightarrow}}w_i[/math]. Если [math]X_i[/math] есть терминал, то [math]w = X_i[/math], a если нетерминал, то порождение [math]X_i \overset{*}{\underset{G'}{\Rightarrow}}w_i[/math] содержит менее [math]n[/math] шагов.
По предположению [math]X_i \overset{*}{\underset{G}{\Rightarrow}}w_i[/math].
Теперь построим соответствующее порождение в [math]G[/math].

[math]A \underset {G}{\Rightarrow} Y_1 Y_2...Y_m \overset{*}{\underset{G}{\Rightarrow}} X_1 X_2...X_k \overset{*}{\underset{G}{\Rightarrow}} w_1 w_2...w_k = w[/math]

Ч.т.д.
[math]\Leftarrow)[/math]
Пусть [math]A \overset{*}{\underset{G}{\Rightarrow}}w[/math]  и  [math]w \ne \varepsilon[/math].
Докажем индукцией по длине порождения, что [math]A \overset{*}{\underset{G'}{\Rightarrow}}w[/math].
Обозначим длину порождения за [math]p[/math].

Базис. [math]p = 1[/math]

[math]A \rightarrow w[/math] является правилом в [math]G[/math]. Поскольку [math]w \ne \varepsilon[/math], эта же правило будет и в [math]G'[/math], поэтому [math]A \overset{*}{\underset{G'}{\Rightarrow}}w[/math].

Предположение. Пусть из [math]A \overset{*}{\underset{G}{\Rightarrow}}w[/math] и [math]w \ne \varepsilon следует, что A \overset{*}{\underset{G'}{\Rightarrow}}w [/math] верно для [math]p \lt n[/math].
Переход. [math]p = n[/math]

Пусть в порождении [math]n[/math] шагов, [math]n \gt 1[/math]. Тогда оно имеет вид [math]A\underset{G}{\Rightarrow}Y_1 Y_2...Y_m \overset{*}{\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 \overset{*}{\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 \overset{*}{\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 \overset{*}{\underset{G}{\Rightarrow}}w_j[/math] содержит менее [math]n[/math] шагов, к ним можно применить предположение индукции и заключить, что если [math]w_j \ne \varepsilon[/math], то [math]Y_j \overset{*}{\underset{G'}{\Rightarrow}}w_j[/math].
Таким образом [math]A \underset{G'}{\rightarrow} X_1 X_2 ... X_k \overset{*}{\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].
[math]\triangleleft[/math]

Литература

  • Хопкрофт Дж., Мотвани Р., Ульман Д.. Введение в теорию автоматов, языков и вычислений, 2-е изд.. : Пер. с англ. ‒ М. : Издательский дом "Вильямс", 2002. ‒ 528 с.