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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Схема алгоритма удаления ε-правил из грамматики)
Строка 1: Строка 1:
== Постановка задачи ==
+
== Используемые определения ==
Дана [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|контекстно-свободная грамматика]]. Необходимо удалить из неё все <tex>\varepsilon</tex>-правила.
 
 
 
== Основные определения ==
 
 
 
 
{{Определение
 
{{Определение
 
|definition = Правила вида <tex>A \to \varepsilon</tex> называются '''<tex>\varepsilon</tex>-правилами'''.
 
|definition = Правила вида <tex>A \to \varepsilon</tex> называются '''<tex>\varepsilon</tex>-правилами'''.
Строка 12: Строка 8:
  
 
== Алгоритм удаления &epsilon;-правил из грамматики ==
 
== Алгоритм удаления &epsilon;-правил из грамматики ==
=== Поиск &epsilon;-порождающих нетерминалов ===
+
'''Вход:''' КС грамматика <tex> G=\langle N,\Sigma, P, S \rangle</tex>.<br/>
''Вход''. КС грамматика <tex> G=\langle N,\Sigma, P, S \rangle</tex>.
+
'''Выход:''' КС грамматика <tex> G'=\langle N,\Sigma, P', S \rangle : L(G') = L(G) \setminus \mathcal {f} \varepsilon \mathcal {g}</tex>.
 
 
''Выход''. Множество <tex>\varepsilon</tex>-порождающих нетерминалов.
 
 
 
''Схема алгоритма:''
 
# Пусть <tex>N_{\varepsilon}</tex> — множество <tex>\varepsilon</tex>-порождающих нетерминалов. Добавить все нетерминалы, из которых непосредственно можно вывести <tex>\mathcal {f} \varepsilon \mathcal {g}</tex>, в множество <tex>N_{\varepsilon}</tex>.
 
# Если найдено правило <tex>A \rightarrow C_1C_2...C_k</tex>, для которого верно, что каждый <tex>C_i</tex> — <tex>\varepsilon</tex>-порождающий нетерминал, то добавить <tex>A</tex> в множество <tex>N_{\varepsilon}</tex>.
 
# Если на шаге 2 множество <tex>N_{\varepsilon}</tex> изменилось, то повторить шаг 2.
 
 
 
{{Теорема
 
|statement = Нетерминал <tex>A</tex> является <tex>\varepsilon</tex>-порождающим тогда и только тогда, если выполнено одно из следующих условий:
 
# в грамматике <tex>G</tex> есть правило <tex>A \rightarrow \varepsilon</tex>;
 
# в грамматике <tex>G</tex> есть правило <tex>A \rightarrow C_1C_2...C_k</tex>, где каждый <tex>C_i</tex> — <tex>\varepsilon</tex>-порождающий нетерминал.
 
|proof = Индукция по длине кратчайшего порождения <tex>A \Rightarrow^* \varepsilon</tex>
 
:''База.'' <tex>A \Rightarrow^* \varepsilon</tex> за один шаг, то есть правило <tex>A \rightarrow\varepsilon</tex>. Следовательно <tex>A</tex> — <tex>\varepsilon</tex>-порождающий нетерминал.
 
 
 
:''Индукция.'' Пусть <tex>A \Rightarrow^* \varepsilon</tex> за <tex>n</tex> шагов. Тогда первыхй шаг порождения <tex>A \rightarrow C_1C_2...C_k</tex>, где <tex>C_i \Rightarrow^* \varepsilon</tex> за менее, чем <tex>n</tex> шагов. По индукционному предположению каждый нетерминал <tex>C_i</tex> обнаруживается как <tex>\varepsilon</tex>-порождающий. Тогда нетерминал <tex>A</tex> — <tex>\varepsilon</tex>-порождающий.
 
}}
 
 
 
=== Схема алгоритма удаления &epsilon;-правил из грамматики ===
 
''Вход.'' КС грамматика <tex> G=\langle N,\Sigma, P, S \rangle</tex>.
 
 
 
''Выход.'' КС грамматика <tex> G'=\langle N,\Sigma, P', S \rangle : L(G') = L(G) \setminus \mathcal {f} \varepsilon \mathcal {g}</tex>.
 
  
''Схема алгоритма:''
+
# [[#.D0.90.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC_.D0.BF.D0.BE.D0.B8.D1.81.D0.BA.D0.B0_.CE.B5-.D0.BF.D0.BE.D1.80.D0.BE.D0.B6.D0.B4.D0.B0.D1.8E.D1.89.D0.B8.D1.85_.D0.BD.D0.B5.D1.82.D0.B5.D1.80.D0.BC.D0.B8.D0.BD.D0.B0.D0.BB.D0.BE.D0.B2 | Найти все <tex>\varepsilon</tex>-порождаюшие нетерминалы]].
# Найти все <tex>\varepsilon</tex>-порождаюшие нетерминалы.
 
 
# Рассмотрим правила вида (*) <tex>A \rightarrow \alpha_0 B_1 \alpha_1 B_2 \alpha_2 ... B_k \alpha_k</tex>, где <tex>\alpha_i</tex> — последовательности из терминалов и нетерминалов, <tex>B_j</tex> — <tex>\varepsilon</tex>-порождающие нетерминалы. Добавить все возможные правила вида (*), в которых либо присутствует, либо отсутствует <tex>B_j\; (1 \le j \le k)</tex>.
 
# Рассмотрим правила вида (*) <tex>A \rightarrow \alpha_0 B_1 \alpha_1 B_2 \alpha_2 ... B_k \alpha_k</tex>, где <tex>\alpha_i</tex> — последовательности из терминалов и нетерминалов, <tex>B_j</tex> — <tex>\varepsilon</tex>-порождающие нетерминалы. Добавить все возможные правила вида (*), в которых либо присутствует, либо отсутствует <tex>B_j\; (1 \le j \le k)</tex>.
 
# Удалить все <tex>\varepsilon</tex>-правила из <tex>P</tex>.
 
# Удалить все <tex>\varepsilon</tex>-правила из <tex>P</tex>.
 +
# Если в исходной грамматике <tex>G</tex> выводилось пустое слово <tex>\varepsilon</tex>, то необходимо добавить новый нетерминал <tex>S'</tex>, сделать его стартовым, добавить правила <tex>S' \rightarrow S|\varepsilon</tex>.
  
''Замечание''
+
=== Доказательство корректности ===
 
 
Если в исходной грамматике <tex>G</tex> выводится пустое слово <tex>\mathcal {f} \varepsilon \mathcal {g}</tex>, то для того, чтобы получить эквивалентную [[Иерархия_Хомского_формальных_грамматик#Неукорачивающие грамматики|грамматику без <tex>\varepsilon</tex>-правил]], необходимо после применения описанного выше алгоритма добавить новый нетерминал <tex>S'</tex>, сделать его стартовым, добавить правила <tex>S' \rightarrow S|\varepsilon</tex>.
 
 
 
== Доказательство корректности алгоритма ==
 
 
{{Теорема
 
{{Теорема
 
|statement = Если грамматика <tex>G'</tex> была построена с помощью описанного выше алгоритма по грамматике <tex>G</tex>, то <tex>L(G') = L(G) \setminus \mathcal {f}\varepsilon \mathcal {g}</tex>.
 
|statement = Если грамматика <tex>G'</tex> была построена с помощью описанного выше алгоритма по грамматике <tex>G</tex>, то <tex>L(G') = L(G) \setminus \mathcal {f}\varepsilon \mathcal {g}</tex>.
Строка 84: Строка 54:
 
Подставив <tex>S</tex> вместо <tex>A</tex> в утверждение (*), видим, что <tex>w \in L(G)</tex> для <tex>w \ne \varepsilon</tex> тогда и только тогда, когда <tex>w \in L(G')</tex>.
 
Подставив <tex>S</tex> вместо <tex>A</tex> в утверждение (*), видим, что <tex>w \in L(G)</tex> для <tex>w \ne \varepsilon</tex> тогда и только тогда, когда <tex>w \in L(G')</tex>.
 
}}
 
}}
 +
 +
== Алгоритм поиска &epsilon;-порождающих нетерминалов ==
 +
'''Вход:''' КС грамматика <tex> G=\langle N,\Sigma, P, S \rangle</tex>.<br/>
 +
'''Выход:''' множество <tex>\varepsilon</tex>-порождающих нетерминалов.
 +
 +
# Пусть <tex>N_{\varepsilon}</tex> — множество <tex>\varepsilon</tex>-порождающих нетерминалов. Добавить все нетерминалы, из которых непосредственно можно вывести <tex>\varepsilon</tex>, в множество <tex>N_{\varepsilon}</tex>.
 +
# Если найдено правило <tex>A \rightarrow C_1C_2...C_k</tex>, для которого верно, что каждый <tex>C_i</tex> — <tex>\varepsilon</tex>-порождающий нетерминал, то добавить <tex>A</tex> в множество <tex>N_{\varepsilon}</tex>.
 +
# Если на шаге 2 множество <tex>N_{\varepsilon}</tex> изменилось, то повторить шаг 2.
 +
 +
 +
{{Теорема
 +
|statement = Нетерминал <tex>A</tex> является <tex>\varepsilon</tex>-порождающим тогда и только тогда, если выполнено одно из следующих условий:
 +
# в грамматике <tex>G</tex> есть правило <tex>A \rightarrow \varepsilon</tex>;
 +
# в грамматике <tex>G</tex> есть правило <tex>A \rightarrow C_1C_2...C_k</tex>, где каждый <tex>C_i</tex> — <tex>\varepsilon</tex>-порождающий нетерминал.
 +
|proof =
 +
Индукция по длине кратчайшего порождения <tex>A \Rightarrow^* \varepsilon</tex>.
 +
 +
'''База.''' <tex>A \Rightarrow \varepsilon</tex>, то есть в грамматике имеется правило <tex>A \rightarrow\varepsilon</tex>. Следовательно, <tex>A</tex> — <tex>\varepsilon</tex>-порождающий нетерминал.
 +
 +
'''Переход.''' Пусть <tex>A \Rightarrow^* \varepsilon</tex> за <tex>n</tex> шагов. Тогда первый шаг порождения <tex>A \rightarrow C_1C_2...C_k</tex>, где <tex>C_i \Rightarrow^* \varepsilon</tex> за менее, чем <tex>n</tex> шагов. По индукционному предположению каждый нетерминал <tex>C_i</tex> обнаруживается как <tex>\varepsilon</tex>-порождающий. Тогда нетерминал <tex>A</tex> — <tex>\varepsilon</tex>-порождающий.
 +
}}
 +
  
 
== Литература ==
 
== Литература ==
 
* ''Хопкрофт Д., Мотвани Р., Ульман Д.''  '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — С. 273: ISBN 5-8459-0261-4 (рус.)
 
* ''Хопкрофт Д., Мотвани Р., Ульман Д.''  '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — С. 273: ISBN 5-8459-0261-4 (рус.)
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]

Версия 23:29, 5 декабря 2011

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

Определение:
Правила вида [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 : L(G') = L(G) \setminus \mathcal {f} \varepsilon \mathcal {g}[/math].

  1. Найти все [math]\varepsilon[/math]-порождаюшие нетерминалы.
  2. Рассмотрим правила вида (*) [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].
  3. Удалить все [math]\varepsilon[/math]-правила из [math]P[/math].
  4. Если в исходной грамматике [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) \setminus \mathcal {f}\varepsilon \mathcal {g}[/math].
Доказательство:
[math]\triangleright[/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]\varepsilon[/math]-правил.
Докажем индукцией по длине порождения, что [math]A \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 \underset{G}{\Rightarrow}^*w[/math], где на шагах после первого, из всех нетерминалов в цепочке [math]\alpha[/math] выводиться [math]\varepsilon[/math].

Предположение. Пусть из [math]A \underset{G'}{\Rightarrow}^*w[/math] следует, что [math]A \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 \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]p[/math].

Базис. [math]p = 1[/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 следует, что A \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 \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].
[math]\triangleleft[/math]

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

Вход: КС грамматика [math] G=\langle N,\Sigma, P, S \rangle[/math].
Выход: множество [math]\varepsilon[/math]-порождающих нетерминалов.

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


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

Индукция по длине кратчайшего порождения [math]A \Rightarrow^* \varepsilon[/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]-порождающий.
[math]\triangleleft[/math]


Литература

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