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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Поиск ε-порождающих нетерминалов)
м (rollbackEdits.php mass rollback)
 
(не показана 101 промежуточная версия 14 участников)
Строка 1: Строка 1:
== Основные определения ==
+
== Используемые определения ==
 
 
 
{{Определение
 
{{Определение
|definition = Правила вида <tex>A \to \varepsilon</tex> называются <tex>\varepsilon</tex>-правилами.
+
|definition = Правила вида <tex>A \to \varepsilon</tex> называются '''<tex>\varepsilon</tex>-правилами''' (англ. ''<tex>\varepsilon</tex>-rule'').
 
}}
 
}}
 
{{Определение
 
{{Определение
|definition = Назовем КС грамматику  <tex>G=(N,\Sigma, P, S)</tex> грамматикой без <tex>\varepsilon</tex>-правил (или неукорачивающей), если либо<br/>
+
|definition = Нетерминал <tex>A</tex> называется '''<tex>\varepsilon</tex>-порождающим''' (англ. ''<tex>\varepsilon</tex>-generating''), если <tex>A \Rightarrow^* \varepsilon</tex>.
:(1) <tex>P</tex> не содержит <tex>\varepsilon</tex>-правил, либо
 
:(2) есть точно одно <tex>\varepsilon</tex>-правило <tex>S \to \varepsilon</tex> и <tex>S</tex> не встречается в правых частях остальных правил из <tex>P</tex>.
 
}}
 
{{Определение
 
|definition = Нетерминал <tex>A</tex> называется <tex>\varepsilon</tex>-порождающим, если <tex>A \overset{*}{\Rightarrow} \varepsilon</tex>.
 
 
}}
 
}}
  
== Алгоритм удаления &epsilon;-правил из грамматики ==
+
== Алгоритм поиска &epsilon;-порождающих нетерминалов ==
=== Поиск &epsilon;-порождающих нетерминалов ===
+
'''Вход:''' КС-грамматика <tex> \Gamma=\langle N,\Sigma, P, S \rangle</tex>.<br/>
''Схема алгоритма:''
+
'''Выход:''' множество <tex>\varepsilon</tex>-порождающих нетерминалов.
:1) Если <tex>A \rightarrow \varepsilon</tex> — правило грамматики <tex>G</tex>, то <tex>A</tex> <tex>\varepsilon</tex>-порождающий нетерминал.
+
 
:2) Если <tex>B \rightarrow C_1C_2...C_k</tex> правило грамматики <tex>G</tex>, где каждый <tex>C_i</tex> <tex>\varepsilon</tex>-порождающий нетерминал, то <tex>B</tex> — <tex>\varepsilon</tex>-порождающий нетерминал.
+
# Найти все <tex>\varepsilon</tex>-правила. Составить множество, состоящее из нетерминалов, входящих в левые части таких правил.
 +
# Перебираем правила грамматики <tex>\Gamma</tex>. Если найдено правило <tex>A \rightarrow C_1C_2 \ldots C_k</tex>, для которого верно, что каждый <tex>C_i</tex> принадлежит множеству, то добавить <tex>A</tex> в множество.
 +
# Если на шаге 2 множество изменилось, то повторить шаг 2.
  
 +
=== Доказательство корректности ===
 
{{Теорема
 
{{Теорема
|statement = Нетерминал <tex>A</tex> является <tex>\varepsilon</tex>-порождающим тогда и только тогда, когда вышеприведенный алгоритм идентифицирует <tex>A</tex> как <tex>\varepsilon</tex>-порождающий.
+
|statement = Описанный выше алгоритм находит все <tex>\varepsilon</tex>-порождающие нетерминалы грамматики <tex>\Gamma</tex>.
|proof = Индукция по длине кратчайшего порождения <tex>A \overset{*}{\Rightarrow} \varepsilon</tex>
+
|proof =
:''База.'' <tex>A \overset{*}{\Rightarrow} \varepsilon</tex> за один шаг, то есть <tex>A \rightarrow\varepsilon</tex>. <tex>\varepsilon</tex>-порождающий нетерминал <tex>A</tex> обнаруживается алгоритмом согласно первому пункту алгоритма.
 
  
:''Индукция.'' Пусть <tex>A \overset{*}{\Rightarrow} \varepsilon</tex> за <tex>n</tex> шагов. Тогда первых шаг порождения <tex>A \rightarrow C_1C_2...C_k</tex>, где <tex>C_i \overset{*}{\Rightarrow} \varepsilon</tex> за менее, чем <tex>n</tex> шагов. По индукционному предположению каждый нетерминал <tex>C_i</tex> обнаруживается как <tex>\varepsilon</tex>-порождающий. Тогда нетерминал <tex>A</tex> обнаружиться вторым пунктом алгоритма как <tex>\varepsilon</tex>-порождающий.
+
Для доказательства корректности алгоритма достаточно показать, что, если множество <tex>\varepsilon</tex>-порождающих нетерминалов на очередной итерации алгоритма не изменялось, то алгоритм нашел все <tex>\varepsilon</tex>-порождающие нетерминалы.
 +
 
 +
Пусть после завершения алгоритма существуют нетерминалы такие, что они являются <tex>\varepsilon</tex>-порождающими, но не были найдены алгоритмом. Выберем из этих нетерминалов нетерминал <tex>B</tex>, из которого выводится <tex>\varepsilon</tex> за наименьшее число шагов. Тогда в грамматике есть правило <tex>B \rightarrow C_1C_2 \ldots C_k</tex>, где каждый нетерминал <tex>C_i</tex> {{---}} <tex>\varepsilon</tex>-порождающий. Каждый <tex>C_i</tex> входит в множество <tex>\varepsilon</tex>-порождающих нетерминалов, так как иначе вместо <tex>B</tex> необходимо было взять <tex>C_i</tex>. Следовательно, на одной из итераций алгоритма <tex>B</tex> уже добавился в множество <tex>\varepsilon</tex>-порождающих нетерминалов. Противоречие. Следовательно, алгоритм находит все <tex>\varepsilon</tex>-порождающие нетерминалы.
 
}}
 
}}
  
=== Схема алгоритма удаления &epsilon;-правил из грамматики ===
+
=== Модификация с очередью ===
''Вход.'' КС грамматика <tex> G=(N,\Sigma, P, S)</tex>.
+
Заведем несколько структур:
 +
*<tex>\mathtt{isEpsilon[nonterm_i]} \ </tex> {{---}} для каждого нетерминала будем хранить пометку, является он <tex>\varepsilon</tex>-порождающим или нет.
 +
*<tex>\mathtt{concernedRules[nonterm_i]} \ </tex> {{---}} для каждого нетерминала будем хранить список номеров тех правил, в правой части которых он встречается;
 +
*<tex>\mathtt{counter[rule_i]} \ </tex> {{---}} для каждого правила будем хранить счетчик количества нетерминалов в правой части, которые еще не помечены <tex>\varepsilon</tex>-порождающими;
 +
*<tex>\mathtt{Q} \ </tex> {{---}} очередь нетерминалов, помеченных <tex>\varepsilon</tex>-порождающими, но еще не обработанных.
 +
 
 +
Сначала проставим <tex>\mathtt{false}</tex> в <tex>\mathtt{isEpsilon} \ </tex> для всех нетерминалов, а в <tex>\mathtt{counter} \ </tex> для каждого правила запишем количество нетерминалов справа от него. Те правила, для которых <tex>\mathtt{counter} \ </tex> сразу же оказался нулевым, добавим в <tex>\mathtt{Q}</tex> и объявим истинным соответствующий <tex>\mathtt{isEpsilon}</tex>, так как это <tex>\varepsilon</tex>-правила. Теперь будем доставать из очереди по одному нетерминалу, смотреть на список <tex>\mathtt{concernedRules} \ </tex> для него и уменьшать <tex>\mathtt{counter}</tex> для всех правил оттуда. Если <tex>\mathtt{counter} \ </tex> какого-то правила в этот момент обнулился, то нетерминал из левой части этого правила помечается <tex>\varepsilon</tex>-порождающим, если еще не был помечен до этого, и добавляется в <tex>\mathtt{Q}</tex>. Продолжаем, пока очередь не станет пустой.
 +
 
 +
=== Время работы алгоритма ===
 +
Базовый алгоритм работает за <tex>O(\left| \Gamma \right| ^ 2)</tex>. В алгоритме с модификацией нетерминал попадает в очередь ровно один раз, соответственно ровно один раз мы пройдемся по списку правил, в правой части которых он лежит. Суммарно получается <tex>O(\left| \Gamma \right|)</tex>.
 +
 
 +
=== Пример ===
 +
Рассмотрим грамматику, причем сразу пронумеруем правила:
 +
#<tex>S\rightarrow ABC</tex>
 +
#<tex>S\rightarrow DS </tex>
 +
#<tex>A\rightarrow \varepsilon</tex>
 +
#<tex>B\rightarrow AC</tex>
 +
#<tex>C\rightarrow \varepsilon</tex>
 +
#<tex>D\rightarrow d</tex>
 +
 
 +
''Поскольку правило 6 содержит справа терминалы, оно заведомо не будет влиять на ответ, поэтому мы не будем его учитывать.''
 +
 
 +
Построим массив списков <tex>\mathtt{concernedRules}</tex>.
 +
{| class="wikitable"
 +
| colspan=5 |<tex>\mathtt{concernedRules}</tex>
 +
|-
 +
!<tex>S</tex>
 +
!<tex>A</tex>
 +
!<tex>B</tex>
 +
!<tex>C</tex>
 +
!<tex>D</tex>
 +
|-
 +
|2
 +
|1, 4
 +
|1
 +
|1, 4
 +
|2
 +
|}
  
''Выход.'' КС грамматика <tex> G'=(N,\Sigma, P', S) : L(G) = L(G') - {\varepsilon}</tex>.
+
{| class="wikitable" style="border:solid 2px gray"
 +
!style="border-right:solid 2px gray"|<tex>\mathtt{Q}</tex>
 +
!style="border-right:solid 2px gray" colspan=5| <tex>\mathtt{isEpsilon}</tex>
 +
!style="border-right:solid 2px gray" colspan=5| <tex>\mathtt{counter}</tex>
 +
!Комментарий
 +
|-
 +
!style="border-top:solid 2px gray; border-right:solid 2px gray" rowspan=2|<tex>\left \{ \right \}</tex>
 +
!style="border-top:solid 2px gray"|<tex>S</tex>
 +
!style="border-top:solid 2px gray"|<tex>A</tex>
 +
!style="border-top:solid 2px gray"|<tex>B</tex>
 +
!style="border-top:solid 2px gray"|<tex>C</tex>
 +
!style="border-top:solid 2px gray; border-right:solid 2px gray"|<tex>D</tex>
 +
!style="border-top:solid 2px gray"|1
 +
!style="border-top:solid 2px gray"|2
 +
!style="border-top:solid 2px gray"|3
 +
!style="border-top:solid 2px gray"|4
 +
!style="border-top:solid 2px gray; border-right:solid 2px gray"|5
 +
|style="border-top:solid 2px gray" rowspan=2|Зададим начальные значения массивам <tex>\mathtt{counter} \ </tex> и <tex>\mathtt{isEpsilon}</tex>.
 +
|-
 +
|0
 +
|0
 +
|0
 +
|0
 +
|style="border-right:solid 2px gray"|0
 +
|3
 +
|2
 +
|0
 +
|2
 +
|style="border-right:solid 2px gray"|0
 +
|-
 +
|style="border-top:solid 2px gray; border-right:solid 2px gray" rowspan=2|<tex>\left \{A,C \right \}</tex>
 +
!style="border-top:solid 2px gray"|<tex>S</tex>
 +
!style="border-top:solid 2px gray"|<tex>A</tex>
 +
!style="border-top:solid 2px gray"|<tex>B</tex>
 +
!style="border-top:solid 2px gray"|<tex>C</tex>
 +
!style="border-top:solid 2px gray; border-right:solid 2px gray"|<tex>D</tex>
 +
!style="border-top:solid 2px gray"|1
 +
!style="border-top:solid 2px gray"|2
 +
!style="border-top:solid 2px gray"|3
 +
!style="border-top:solid 2px gray"|4
 +
!style="border-top:solid 2px gray; border-right:solid 2px gray"|5
 +
|style="border-top:solid 2px gray" rowspan=2 |Заметим, что правила 3 и 5 являются <tex>\varepsilon</tex>-правилами. Пометим левые нетерминалы из этих правил и добавим их в очередь. После этого в <tex>\mathtt{Q}</tex> лежит <tex>A</tex> и <tex>C</tex>, а <tex>\mathtt{counter} \ </tex> остался без изменений.
 +
|-
 +
|0
 +
|1
 +
|0
 +
|1
 +
|style="border-right:solid 2px gray"|0
 +
|3
 +
|2
 +
|0
 +
|2
 +
|style="border-right:solid 2px gray"|0
 +
|-
 +
|style="border-top:solid 2px gray; border-right:solid 2px gray" rowspan=2|<tex>\left\{C \right\}</tex>
 +
!style="border-top:solid 2px gray"|<tex>S</tex>
 +
!style="border-top:solid 2px gray"|<tex>A</tex>
 +
!style="border-top:solid 2px gray"|<tex>B</tex>
 +
!style="border-top:solid 2px gray"|<tex>C</tex>
 +
!style="border-top:solid 2px gray; border-right:solid 2px gray"|<tex>D</tex>
 +
!style="border-top:solid 2px gray"|1
 +
!style="border-top:solid 2px gray"|2
 +
!style="border-top:solid 2px gray"|3
 +
!style="border-top:solid 2px gray"|4
 +
!style="border-top:solid 2px gray; border-right:solid 2px gray"|5
 +
|style="border-top:solid 2px gray" rowspan=2|Достанем из очереди <tex>A</tex>, декрементируем те счетчики, которые относятся к связанным с ним правилам. К очереди ничего не добавится.
 +
|-
 +
|0
 +
|1
 +
|0
 +
|1
 +
|style="border-right:solid 2px gray"|0
 +
|2
 +
|2
 +
|0
 +
|1
 +
|style="border-right:solid 2px gray"|0
 +
|-
 +
|style="border-top:solid 2px gray; border-right:solid 2px gray" rowspan=2|<tex>\left\{B \right\}</tex>
 +
!style="border-top:solid 2px gray"|<tex>S</tex>
 +
!style="border-top:solid 2px gray"|<tex>A</tex>
 +
!style="border-top:solid 2px gray"|<tex>B</tex>
 +
!style="border-top:solid 2px gray"|<tex>C</tex>
 +
!style="border-top:solid 2px gray; border-right:solid 2px gray"|<tex>D</tex>
 +
!style="border-top:solid 2px gray"|1
 +
!style="border-top:solid 2px gray"|2
 +
!style="border-top:solid 2px gray"|3
 +
!style="border-top:solid 2px gray"|4
 +
!style="border-top:solid 2px gray; border-right:solid 2px gray"|5
 +
|style="border-top:solid 2px gray" rowspan=2|Достанем из очереди <tex>C</tex>. После проведения действий из алгоритма в очередь добавится <tex>B</tex>.
 +
|-
 +
|0
 +
|1
 +
|1
 +
|1
 +
|style="border-right:solid 2px gray"|0
 +
|1
 +
|2
 +
|0
 +
|0
 +
|style="border-right:solid 2px gray"|0
 +
|-
 +
|style="border-top:solid 2px gray; border-right:solid 2px gray" rowspan=2|<tex>\left\{S \right\}</tex>
 +
!style="border-top:solid 2px gray"|<tex>S</tex>
 +
!style="border-top:solid 2px gray"|<tex>A</tex>
 +
!style="border-top:solid 2px gray"|<tex>B</tex>
 +
!style="border-top:solid 2px gray"|<tex>C</tex>
 +
!style="border-top:solid 2px gray; border-right:solid 2px gray"|<tex>D</tex>
 +
!style="border-top:solid 2px gray"|1
 +
!style="border-top:solid 2px gray"|2
 +
!style="border-top:solid 2px gray"|3
 +
!style="border-top:solid 2px gray"|4
 +
!style="border-top:solid 2px gray; border-right:solid 2px gray"|5
 +
|style="border-top:solid 2px gray" rowspan=2|Достанем из очереди <tex>B</tex>. После действий алгоритма в очередь добавится <tex>S</tex>.
 +
|-
 +
|1
 +
|1
 +
|1
 +
|1
 +
|style="border-right:solid 2px gray"|0
 +
|0
 +
|2
 +
|0
 +
|0
 +
|style="border-right:solid 2px gray"|0
 +
|-
 +
|style="border-top:solid 2px gray; border-right:solid 2px gray" rowspan=2|<tex>\left\{ \right\}</tex>
 +
!style="border-top:solid 2px gray"|<tex>S</tex>
 +
!style="border-top:solid 2px gray"|<tex>A</tex>
 +
!style="border-top:solid 2px gray"|<tex>B</tex>
 +
!style="border-top:solid 2px gray"|<tex>C</tex>
 +
!style="border-top:solid 2px gray; border-right:solid 2px gray"|<tex>D</tex>
 +
!style="border-top:solid 2px gray"|1
 +
!style="border-top:solid 2px gray"|2
 +
!style="border-top:solid 2px gray"|3
 +
!style="border-top:solid 2px gray"|4
 +
!style="border-top:solid 2px gray; border-right:solid 2px gray"|5
 +
|style="border-top:solid 2px gray" rowspan=2|Достанем из очереди <tex>S</tex>. Ничего не добавится в очередь и она останется пустой. Алгоритм закончил свое выполнение. Итого в множество <tex>\varepsilon</tex>-правил входят все нетерминалы, кроме <tex>D</tex>.
 +
|-
 +
|1
 +
|1
 +
|1
 +
|1
 +
|style="border-right:solid 2px gray"|0
 +
|0
 +
|1
 +
|0
 +
|0
 +
|style="border-right:solid 2px gray"|0
 +
|}
  
''Схема алгоритма:''
+
Если применять алгоритм без модификации с очередью, то действия будут следующие:
:1) Найти все <tex>\varepsilon</tex>-порождаюшие нетерминалы.
+
# Возьмём множество состоящее из <tex>\varepsilon</tex>-порождающих нетерминалов <tex>\lbrace A, C \rbrace</tex>.
:2) Удалить все <tex>\varepsilon</tex>-правила из <tex>P</tex>.
+
# Добавим <tex>B</tex> в множество, так как правая часть правила <tex>B\rightarrow AC</tex> состоит только из нетерминалов из множества.
:3) Рассмотрим правила вида (*)<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</tex>, кроме правила <tex>A \rightarrow \varepsilon</tex>. Такое правило может возникнуть, если все <tex>\alpha_i = \varepsilon</tex>.
+
# Повторим второй пункт для правила <tex>S\rightarrow ABC</tex> и получим множество <tex>\lbrace A, B, C, S \rbrace</tex>.
 +
# Больше нет нерассмотренных правил, содержащих справа только нетерминалы из множества.
  
''Замечание''
+
Таким образом <tex>\varepsilon</tex>-порождающими нетерминалами являются <tex>A</tex>, <tex>B</tex>, <tex>C</tex> и <tex>S</tex>.
 +
 
 +
== Алгоритм удаления &epsilon;-правил из грамматики ==
 +
'''Вход:''' КС-грамматика <tex> \Gamma=\langle N,\Sigma, P, S \rangle</tex>.<br/>
 +
'''Выход:''' КС-грамматика <tex> \Gamma'=\langle N,\Sigma, P', S' \rangle</tex> без <tex>\varepsilon</tex>-правил (может присутствовать правило <tex>S \rightarrow \varepsilon</tex>, но в этом случае <tex>S</tex> не встречается в правых частях правил); <tex>L(\Gamma') = L(\Gamma)</tex>.
  
Если в исходной грамматике <tex>G</tex> есть правило <tex>S \rightarrow \varepsilon</tex> и <tex>S</tex> встречается в правых частях, то для того, чтобы получить эквивалентную грамматику без <tex>\varepsilon</tex>-правил, необходимо после применения описанного выше алгоритма добавить новый нетерминал <tex>S'</tex>, сделать его стартовым, добавить правила <tex>S' \rightarrow S|\varepsilon</tex>.
+
# Добавить все правила из <tex>P</tex> в <tex>P'</tex>.
 +
# Найти все <tex>\varepsilon</tex>-порождаюшие нетерминалы.
 +
# Для каждого правила вида <tex>A \rightarrow \alpha_0 B_1 \alpha_1 B_2 \alpha_2 \ldots B_k \alpha_k \ </tex> (где <tex>\alpha_i</tex> — последовательности из терминалов и нетерминалов, <tex>B_j</tex> — <tex>\varepsilon</tex>-порождающие нетерминалы) добавить в <tex>P'</tex> все возможные варианты правил, в которых либо присутствует, либо удалён каждый из нетерминалов <tex>B_j\; (1 \leqslant j \leqslant k)</tex>.
 +
# Удалить все <tex>\varepsilon</tex>-правила из <tex>P'</tex>.
 +
# Если в исходной грамматике <tex>\Gamma</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) - \varepsilon</tex>.
+
|statement = Если грамматика <tex>\Gamma'</tex> была построена с помощью описанного выше алгоритма по грамматике <tex>\Gamma</tex>, то <tex>L(\Gamma') = L(\Gamma)</tex>.
 
|proof =
 
|proof =
 +
Сначала докажем, что, если не выполнять шаг 5 алгоритма, то получится грамматика <tex>\Gamma' : L(\Gamma') = L(\Gamma) \setminus \lbrace \varepsilon \rbrace </tex>.<br/>
 
Для этого достаточно доказать, что
 
Для этого достаточно доказать, что
<tex>A \overset{*}{\underset{G'}{\Rightarrow}}w</tex> тогда и только тогда, когда <tex>A \overset{*}{\underset{G}{\Rightarrow}}w</tex> и <tex>w \ne \varepsilon</tex>(*).
+
<tex>A \underset{\Gamma'}{\Rightarrow}^*w</tex> тогда и только тогда, когда <tex>A \underset{\Gamma}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex> (*).
 +
 
 +
<tex>\Rightarrow</tex>
 +
Пусть <tex>A \underset{\Gamma'}{\Rightarrow}^*w</tex>&nbsp; и&nbsp; <tex>w \ne \varepsilon</tex>.<br/>
 +
Докажем индукцией по длине порождения в грамматике <tex>\Gamma'</tex>, что <tex>A \underset{\Gamma}{\Rightarrow}^*w</tex>.<br/>
 +
'''База'''. <tex>A \underset{\Gamma'}{\Rightarrow} w</tex>.<br/>
 +
В этом случае в <tex>\Gamma'</tex> есть правило <tex>A \rightarrow w</tex>. По построению <tex>\Gamma'</tex> в <tex>\Gamma</tex> есть правило <tex>A \rightarrow \alpha</tex>, причем <tex>\alpha</tex> — цепочка <tex>w</tex>, элементы которой, возможно, перемежаются <tex>\varepsilon</tex>-порождающими нетерминалами. Тогда в <tex>\Gamma</tex> есть порождения <tex>A \underset{\Gamma}{\Rightarrow} \alpha \underset{\Gamma}{\Rightarrow}^*w</tex>.<br/>
 +
'''Предположение индукции'''. Пусть из <tex>A \underset{\Gamma'}{\Rightarrow}^*w \ne \varepsilon</tex> менее, чем за <tex>n</tex> шагов, следует, что <tex>A \underset{\Gamma}{\Rightarrow}^*w</tex>.<br/>
 +
'''Переход'''.
 +
Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{\Gamma'}{\Rightarrow}X_1 X_2 \ldots X_k \underset{\Gamma'}{\Rightarrow}^*w</tex>, где <tex>X_i \in N \cup \Sigma </tex>. Первое использованное правило должно быть построено по правилу грамматики <tex>\Gamma</tex> <tex>A \rightarrow Y_1 Y_2 \ldots Y_m</tex>, где последовательность <tex>Y_1 Y_2 \ldots Y_m</tex> совпадает с последовательностью <tex>X_1 X_2 \ldots X_k</tex>, символы которой, возможно, перемежаются <tex>\varepsilon</tex>-порождающими нетерминалами.<br/>
 +
Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2 \ldots w_k</tex>, где <tex>X_i \underset{\Gamma'}{\Rightarrow}^*w_i</tex>. Если <tex>X_i</tex> — терминал, то <tex>w_i = X_i</tex>, a если нетерминал, то порождение <tex>X_i \underset{\Gamma'}{\Rightarrow}^*w_i</tex> содержит менее <tex>n</tex> шагов. По предположению <tex>X_i \underset{\Gamma}{\Rightarrow}^*w_i</tex>, значит <tex>A \underset {\Gamma}{\Rightarrow} Y_1 Y_2 \ldots Y_m \underset{\Gamma}{\Rightarrow}^* X_1 X_2 \ldots X_k \underset{\Gamma}{\Rightarrow}^* w_1 w_2 \ldots w_k = w</tex>.
  
<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>p</tex>.
 
:'''Базис'''. <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>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>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/>
 
Цепочку <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>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/>
 
Ч.т.д.<br/>
 
 
<tex>\Leftarrow</tex><br/>
 
<tex>\Leftarrow</tex><br/>
Пусть <tex>A \overset{*}{\underset{G}{\Rightarrow}}w</tex>&nbsp; и&nbsp; <tex>w \ne \varepsilon</tex>.<br/>  
+
Пусть <tex>A \underset{\Gamma}{\Rightarrow}^*w</tex>&nbsp; и&nbsp; <tex>w \ne \varepsilon</tex>.<br/>  
Докажем индукцией по длине порождения, что <tex>A \overset{*}{\underset{G'}{\Rightarrow}}w</tex>.<br/>  
+
Докажем индукцией по длине порождения в грамматике <tex>\Gamma</tex>, что <tex>A \underset{\Gamma'}{\Rightarrow}^*w</tex>.<br/>  
Обозначим длину порождения за <tex>p</tex>.<br/>
+
'''База'''. <tex>A \underset{\Gamma}{\Rightarrow} w</tex>.<br/>
:'''Базис'''. <tex>p = 1</tex><br/>
+
Правило <tex>A \rightarrow w</tex> присутствует в <tex>\Gamma</tex>. Поскольку <tex>w \ne \varepsilon</tex>, это же правило будет и в <tex>\Gamma'</tex>, поэтому <tex>A \underset{\Gamma'}{\Rightarrow}^*w</tex>.<br/>
<tex>A \rightarrow w</tex> является правилом в <tex>G</tex>. Поскольку <tex>w \ne \varepsilon</tex>, эта же правило будет и в <tex>G'</tex>, поэтому <tex>A \overset{*}{\underset{G'}{\Rightarrow}}w</tex>.
+
'''Предположение индукции'''. Пусть из <tex>A \underset{\Gamma}{\Rightarrow}^*w \ne \varepsilon</tex> менее, чем за <tex>n</tex> шагов, следует, что <tex>A \underset{\Gamma'}{\Rightarrow}^*w </tex>.<br/>
:'''Предположение'''. Пусть из <tex>A \overset{*}{\underset{G}{\Rightarrow}}w</tex> и <tex>w \ne \varepsilon следует, что A \overset{*}{\underset{G'}{\Rightarrow}}w </tex> верно для <tex>p < n</tex>.<br/>
+
'''Переход'''. Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{\Gamma}{\Rightarrow}Y_1 Y_2 \ldots Y_m \underset{\Gamma}{\Rightarrow}^*w</tex>, где <tex>Y_i \in N \cup \Sigma </tex>. Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2 \ldots w_m</tex>, где <tex>Y_i \underset{\Gamma}{\Rightarrow}^*w_i</tex>.<br/>
:'''Переход'''. <tex>p = n</tex><br/>
+
Пусть <tex>Y_{i_1}, Y_{i_2}, \ldots, Y_{i_p}</tex> — подпоследовательность, состоящая из всех элементов, таких, что <tex>w_{i_k} \ne \varepsilon</tex>, то есть <tex>Y_{i_1} Y_{i_2} \ldots Y_{i_p} \underset{\Gamma}{\Rightarrow}^*w</tex>. <tex>p \geqslant 1</tex>, поскольку <tex>w \ne \varepsilon</tex>. Значит, <tex>A \rightarrow Y_{i_1} Y_{i_2} \ldots Y_{i_p}</tex> является правилом в <tex>\Gamma'</tex> по построению <tex>\Gamma'</tex>.<br/>
Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G}{\Rightarrow}Y_1 Y_2...Y_m
+
Так как каждое из порождений <tex>Y_i \underset{\Gamma}{\Rightarrow}^*w_i</tex> содержит менее <tex>n</tex> шагов, к ним можно применить предположение индукции и заключить, что, если <tex>w_i \ne \varepsilon</tex>, то <tex>Y_i \underset{\Gamma'}{\Rightarrow}^*w_i</tex>.<br/>
\overset{*}{\underset{G}{\Rightarrow}}w</tex>, где <tex>Y_i \in N \cup \Sigma </tex>. Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2...w_m</tex>, где <tex>Y_i \overset{*}{\underset{G'}{\Rightarrow}}w_i</tex>.<br/>
+
Таким образом, <tex>A \underset{\Gamma'}{\Rightarrow} Y_{i_1} Y_{i_2} \ldots Y_{i_p} \underset{\Gamma'}{\Rightarrow}^* w</tex>.
Пусть <tex>X_1, X_2, ... X_k</tex> будут теми из <tex>Y_j</tex>(в порядке записи), для которых <tex>w_i \ne \varepsilon</tex>. <tex>k \ge 1</tex>, поскольку <tex>w \ne \varepsilon</tex>.<br/> Таким образом <tex>A \rightarrow X_1 X_2 ... X_k</tex> является правилом в <tex>G'</tex> по построению <tex>G'</tex>.  
 
Утверждаем, что <tex> X_1 X_2...X_k \overset{*}{\underset{G}{\Rightarrow}}w</tex>, поскольку только <tex>Y_j</tex>, которых нет среди <tex>X_1, X_2, ... X_k</tex>, использованы для порождения <tex>\varepsilon</tex> и не вносят ничего в порождение <tex>w</tex>.
 
Так как каждое из порождений <tex>Y_j \overset{*}{\underset{G}{\Rightarrow}}w_j</tex> содержит менее <tex>n</tex> шагов, к ним можно применить предположение индукции и заключить, что если <tex>w_j \ne \varepsilon</tex>, то <tex>Y_j \overset{*}{\underset{G'}{\Rightarrow}}w_j</tex>.<br/>
 
Таким образом <tex>A \underset{G'}{\rightarrow} X_1 X_2 ... X_k \overset{*}{\underset{G'}{\Rightarrow}} w</tex>.<br/>
 
Ч.т.д.
 
  
Подставив <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(\Gamma)</tex> для <tex>w \ne \varepsilon</tex> тогда и только тогда, когда <tex>w \in L(\Gamma')</tex>. Так как после выполнения шага 5 алгоритма в <tex>\Gamma'</tex> могло добавиться только пустое слово <tex>\varepsilon</tex>, то язык, задаваемый КС-грамматикой <tex>\Gamma'</tex>, совпадает с языком, задаваемым КС-грамматикой <tex>\Gamma</tex>.
 
}}
 
}}
  
== Литература ==
+
=== Время работы алгоритма ===
* Ахо Альфред, Джеффри Ульман. Теория Синтаксического Анализа, Перевода и Компиляции. Том 1.
+
Рассмотрим грамматику <tex>\Gamma</tex>:
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.
+
:<tex>S\rightarrow T_1 T_2 T_3 \ldots T_n</tex>
 +
:<tex>T_1\rightarrow t_1|\varepsilon</tex>
 +
:<tex>T_2\rightarrow t_2|\varepsilon</tex>
 +
:<tex>\ldots\</tex>
 +
:<tex>T_n\rightarrow t_n|\varepsilon</tex>
 +
 
 +
<tex>\left| \Gamma \right| = O(n)</tex>. Из нетерминала <tex>S</tex> можно вывести <tex>2^n</tex> сочетаний нетерминалов <tex>T_i</tex>. Таким образом в худшем случае алгоритм работает за <tex>O(2^{\left| \Gamma \right|})</tex>.<br>
 +
Рассмотрим теперь грамматику с устраненными [[Удаление_длинных_правил_из_грамматики|длинными правилами]]. После применения данного алгоритма, который работает за <tex>O(\left| \Gamma \right|)</tex>, в грамматике станет на <tex>O(\left| \Gamma \right|)</tex> больше правил, но при этом все они будут размером <tex>O(1)</tex>. Итого по-прежнему  <tex>\left| \Gamma \right| = O(n)</tex>. Однако алгоритм удаления <tex>\varepsilon</tex>-правил будет работать за <tex>O(\left| \Gamma \right|)</tex>, поскольку для каждого правила можно будет добавить только <tex>O(1)</tex> сочетаний нетерминалов.
 +
 
 +
=== Пример ===
 +
Рассмотрим грамматику:
 +
:<tex>S\rightarrow ABCd</tex>
 +
:<tex>A\rightarrow a|\varepsilon</tex>
 +
:<tex>B\rightarrow AC</tex>
 +
:<tex>C\rightarrow c|\varepsilon</tex>
 +
 
 +
В ней <tex>A</tex>, <tex>B</tex> и <tex>C</tex> являются <tex>\varepsilon</tex>-порождающими нетерминалами.
 +
# Переберём для каждого правила все возможные сочетания &epsilon;-порождающих нетерминалов и добавим новые правила:
 +
#* <tex>S\rightarrow Ad|ABd|ACd|Bd|BCd|Cd|d</tex> для <tex>S \rightarrow ABCd</tex>
 +
#* <tex>B \rightarrow A|C</tex> для <tex>B \rightarrow AC</tex>
 +
# Удалим праила <tex>A\rightarrow \varepsilon</tex> и <tex>C\rightarrow \varepsilon</tex>
 +
 
 +
В результате мы получим новую грамматику без <tex>\varepsilon</tex>-правил:
 +
:<tex>S\rightarrow Ad|ABd|ACd|ABCd|Bd|BCd|Cd|d</tex>
 +
:<tex>A\rightarrow a</tex>
 +
:<tex>B\rightarrow A|AC|C</tex>
 +
:<tex>C\rightarrow c</tex>
 +
 
 +
== См. также  ==
 +
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
 +
* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]
 +
 
 +
== Источники информации ==
 +
* ''Хопкрофт Д., Мотвани Р., Ульман Д.''  '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — С. 273: ISBN 5-8459-0261-4 (рус.)
 +
* [http://en.wikipedia.org/wiki/Chomsky_normal_form Wikipedia — Chomsky normal form]
 +
 
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Контекстно-свободные грамматики]]
 +
[[Категория: Нормальные формы КС-грамматик]]

Текущая версия на 19:28, 4 сентября 2022

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

Определение:
Правила вида [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]-порождающих нетерминалов.

  1. Найти все [math]\varepsilon[/math]-правила. Составить множество, состоящее из нетерминалов, входящих в левые части таких правил.
  2. Перебираем правила грамматики [math]\Gamma[/math]. Если найдено правило [math]A \rightarrow C_1C_2 \ldots C_k[/math], для которого верно, что каждый [math]C_i[/math] принадлежит множеству, то добавить [math]A[/math] в множество.
  3. Если на шаге 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 \ldots 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].

Пример

Рассмотрим грамматику, причем сразу пронумеруем правила:

  1. [math]S\rightarrow ABC[/math]
  2. [math]S\rightarrow DS [/math]
  3. [math]A\rightarrow \varepsilon[/math]
  4. [math]B\rightarrow AC[/math]
  5. [math]C\rightarrow \varepsilon[/math]
  6. [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

Если применять алгоритм без модификации с очередью, то действия будут следующие:

  1. Возьмём множество состоящее из [math]\varepsilon[/math]-порождающих нетерминалов [math]\lbrace A, C \rbrace[/math].
  2. Добавим [math]B[/math] в множество, так как правая часть правила [math]B\rightarrow AC[/math] состоит только из нетерминалов из множества.
  3. Повторим второй пункт для правила [math]S\rightarrow ABC[/math] и получим множество [math]\lbrace A, B, C, S \rbrace[/math].
  4. Больше нет нерассмотренных правил, содержащих справа только нетерминалы из множества.

Таким образом [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].

  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 \ldots 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].
  4. Удалить все [math]\varepsilon[/math]-правила из [math]P'[/math].
  5. Если в исходной грамматике [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 \ldots 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 \ldots Y_m[/math], где последовательность [math]Y_1 Y_2 \ldots Y_m[/math] совпадает с последовательностью [math]X_1 X_2 \ldots X_k[/math], символы которой, возможно, перемежаются [math]\varepsilon[/math]-порождающими нетерминалами.
Цепочку [math]w[/math] можно разбить на [math]w_1 w_2 \ldots 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 \ldots Y_m \underset{\Gamma}{\Rightarrow}^* X_1 X_2 \ldots X_k \underset{\Gamma}{\Rightarrow}^* w_1 w_2 \ldots 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 \ldots Y_m \underset{\Gamma}{\Rightarrow}^*w[/math], где [math]Y_i \in N \cup \Sigma [/math]. Цепочку [math]w[/math] можно разбить на [math]w_1 w_2 \ldots w_m[/math], где [math]Y_i \underset{\Gamma}{\Rightarrow}^*w_i[/math].
Пусть [math]Y_{i_1}, Y_{i_2}, \ldots, Y_{i_p}[/math] — подпоследовательность, состоящая из всех элементов, таких, что [math]w_{i_k} \ne \varepsilon[/math], то есть [math]Y_{i_1} Y_{i_2} \ldots 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} \ldots 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} \ldots 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]-порождающими нетерминалами.

  1. Переберём для каждого правила все возможные сочетания ε-порождающих нетерминалов и добавим новые правила:
    • [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]
  2. Удалим праила [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