Изменения

Перейти к: навигация, поиск

Удаление eps-правил из грамматики

14 546 байт добавлено, 19:28, 4 сентября 2022
м
rollbackEdits.php mass rollback
== Основные Используемые определения == 
{{Определение
|definition = Правила вида <tex>A \to \varepsilon</tex> называются '''<tex>\varepsilon</tex>-правилами''' (англ. ''<tex>\varepsilon</tex>-rule'').
}}
{{Определение
|definition = Назовем КС-грамматику Нетерминал <tex>G=(N,\Sigma, P, S)A</tex> грамматикой без называется '''<tex>\varepsilon</tex>-правил порождающим''' (или неукорачивающей), если либо<br/>:(1) <tex>P</tex> не содержит англ. ''<tex>\varepsilon</tex>-правилgenerating''), либо :(2) есть точно одно если <tex>A \varepsilon</tex>-правило <tex>S \to Rightarrow^* \varepsilon</tex> и <tex>S</tex> не встречается в правых частях остальных правил из <tex>P</tex>.
}}
 == Алгоритм поиска &epsilon;-порождающих нетерминалов =='''Вход:''' КС-грамматика <tex> \Gamma=\langle N,\Sigma, P, S \rangle</tex>.<br/>'''Выход:''' множество <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. === Доказательство корректности ==={{ОпределениеТеорема|definition statement = Нетерминал Описанный выше алгоритм находит все <tex>\varepsilon</tex>-порождающие нетерминалы грамматики <tex>\Gamma</tex>A.|proof = Для доказательства корректности алгоритма достаточно показать, что, если множество <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>A \Rightarrow^* varepsilon</tex>-порождающих нетерминалов. Противоречие. Следовательно, алгоритм находит все <tex>\varepsilon</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
|}
 
{| 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
|}
 
Если применять алгоритм без модификации с очередью, то действия будут следующие:
# Возьмём множество состоящее из <tex>\varepsilon</tex>-порождающих нетерминалов <tex>\lbrace A, C \rbrace</tex>.
# Добавим <tex>B</tex> в множество, так как правая часть правила <tex>B\rightarrow AC</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;-правил из грамматики ==
=== Поиск &epsilon;'''Вход:''' КС-порождающих нетерминалов ===:1) Если грамматика <tex>A \rightarrow Gamma=\langle N,\Sigma, P, S \varepsilonrangle</tex> — правило грамматики .<texbr/>G'''Выход:''' КС-грамматика </tex>\Gamma'=\langle N, то <tex>A\Sigma, P', S' \rangle</tex> без <tex>\varepsilon</tex>-порождающий нетерминал.:2) Если правил (может присутствовать правило <tex>B S \rightarrow C_1C_2...C_k</tex> — правило грамматики <tex>G</tex>, где каждый <tex>C_i</tex> — <tex>\varepsilon</tex>-порождающий нетерминал, то но в этом случае <tex>BS</tex> не встречается в правых частях правил); <tex>L(\varepsilonGamma') = L(\Gamma)</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>A\Gamma'</tex> является была построена с помощью описанного выше алгоритма по грамматике <tex>\varepsilonGamma</tex>-порождающим тогда и только тогда, когда вышеприведенный алгоритм идентифицирует <tex>A</tex> как то <tex>L(\Gamma') = L(\varepsilonGamma)</tex>-порождающий.|proof = Индукция по длине кратчайшего порождения Сначала докажем, что, если не выполнять шаг 5 алгоритма, то получится грамматика <tex>A \Rightarrow^*Gamma' : L(\Gamma') = L(\Gamma) \setminus \lbrace \varepsilon\rbrace </tex>.<br/>:''База.'' Для этого достаточно доказать, что<tex>A \underset{\Gamma'}{\Rightarrow}^*\varepsilonw</tex> за один шагтогда и только тогда, то есть когда <tex>A \rightarrowunderset{\Gamma}{\varepsilonRightarrow}^*w</tex>. и <tex>w \ne \varepsilon</tex>-порождающий нетерминал <tex>A</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>\varepsilonalpha</tex> — цепочка <tex>w</tex> за , элементы которой, возможно, перемежаются <tex>n\varepsilon</tex> шагов-порождающими нетерминалами. Тогда первых шаг в <tex>\Gamma</tex> есть порождения <tex>A \rightarrow C_1C_2underset{\Gamma}{\Rightarrow} \alpha \underset{\Gamma}{\Rightarrow}^*w</tex>...C_k<br/tex>, где '''Предположение индукции'''. Пусть из <tex>C_i A \underset{\Gamma'}{\Rightarrow}^* w \ne \varepsilon</tex> за менее, чем за <tex>n</tex> шагов, следует, что <tex>A \underset{\Gamma}{\Rightarrow}^*w</tex>. По индукционному предположению каждый нетерминал <br/>'''Переход'''.Пусть в порождении <tex>n</tex> шагов, <tex>C_in > 1</tex> обнарудивается как . Тогда оно имеет вид <tex>A\underset{\Gamma'}{\varepsilonRightarrow}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> G=(N,\Sigma, P, S)</tex>.
:''Выход''. Эквивалентная КС-грамматика <tex> G'=(N',\Sigma, P', S') </tex> без <tex>\varepsilon</tex>-правил.
:''Метод''.
(1) Построить <tex>N_e=\{A \mid A \in N</tex> и <tex>A \Rightarrow_{G}^{*}\varepsilon\}</tex>.
(2) Построить <tex>P'</tex> так:
Если <tex>A \rightarrow \alpha_0 B_1 \alpha_1 B_2 \alpha_2 ... B_k \alpha_k \in P, k \geqslant 0</tex> и <tex>B_i \in N_e</tex> для <tex>1 \leqslant i \leqslant k</tex>,
но ни один символ в цепочках <tex>a_j (0 \leqslant j \leqslant k) \notin N_e</tex>, то включить в <tex>P'</tex> все правила
вида <tex>A \rightarrow \alpha_0 X_1 \alpha_1 X_2 \alpha_2 ... X_k \alpha_k</tex>
где <tex>X_i-</tex> либо <tex>B_i</tex>, либо <tex>\varepsilon</tex>, но не включать правило <tex>A \rightarrow \varepsilon</tex> (это могло бы произойти
в случае, если все <tex>\alpha_i</tex> равны <tex>\varepsilon</tex>).
(3) Если <tex>S \in N_e</tex>, включить в <tex>P'</tex> правила
<tex>S' \rightarrow \varepsilon \mid S</tex>
где <tex>S'-</tex> новый символ, и положить <tex>N'=N \cup \{ S' \}</tex>. В противном случае
положить <tex>N'=N</tex> и <tex>S'=S</tex>.
(4) Положить <tex> G'=(N',\Sigma, P', S')</tex>. <tex>\Box</tex>
Для доказательства корректности нам понадобиться следующее утверждение:
{{Утверждение
|statement= <tex>A \overset{*}{\underset{G'}{\Rightarrow}}w</tex> <tex>(A \ne S')</tex>&nbsp; тогда и только тогда, когда <tex>A \overset{*}{\underset{G}{\Rightarrow}}w</tex>&nbsp; и&nbsp; <tex>w \ne \varepsilon</tex>
|proof=
<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 \ne S')]</tex>&nbsp; <tex>\Rightarrow [A \overset{*}{\underset{G}{\Rightarrow}}w</tex>&nbsp; и&nbsp; <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>A \overset{*}underset{\underset{GGamma}{\Rightarrow}}^*w</tex>&nbsp; и&nbsp; <tex>w \ne \varepsilon</tex>.<br/> Докажем индукцией по длине порожденияв грамматике <tex>\Gamma</tex>, что <tex>A \overset{*}underset{\underset{GGamma'}{\Rightarrow}}^*w</tex>.<br/> Обозначим длину порождения за <tex>p</tex>.<br/>:'''БазисБаза'''. <tex>p = 1A \underset{\Gamma}{\Rightarrow} w</tex>.<br/>Правило <tex>A \rightarrow w</tex> является правилом присутствует в <tex>G\Gamma</tex>. Поскольку <tex>w \ne \varepsilon</tex>, эта это же правило будет и в <tex>G\Gamma'</tex>, поэтому <tex>A \overset{*}underset{\underset{GGamma'}{\Rightarrow}}^*w</tex>.<br/>:'''Предположениеиндукции'''. Пусть из <tex>[A \overset{*}underset{\underset{GGamma}{\Rightarrow}}^*w\ne \varepsilon</tex>&nbsp; и&nbsp; менее, чем за <tex>n</tex> шагов, следует, что <tex>w \ne \varepsilon] \Rightarrow [A \overset{*}underset{\underset{GGamma'}{\Rightarrow}}^*w (A \ne S')]</tex>&nbsp; верно для <tex>p < n</tex>.<br/>:'''Переход'''. <tex>p = n</tex><br/>Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G\Gamma}{\Rightarrow}Y_1 Y_2...\ldots Y_m\overset{*}underset{\underset{GGamma}{\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 \overset{*}underset{\underset{G'Gamma}{\Rightarrow}}^*w_i</tex>.<br/>Пусть <tex>X_1Y_{i_1}, X_2Y_{i_2}, ... X_k\ldots, Y_{i_p}</tex> будут теми — подпоследовательность, состоящая из всех элементов, таких, что <tex>Y_jw_{i_k} \ne \varepsilon</tex>(в порядке записи), для которых то есть <tex>w_i Y_{i_1} Y_{i_2} \ldots Y_{i_p} \underset{\ne Gamma}{\varepsilonRightarrow}^*w</tex>. <tex>k p \ge geqslant 1</tex>, поскольку <tex>w \ne \varepsilon</tex>.<br/> Таким образом Значит, <tex>A \rightarrow X_1 X_2 ... X_kY_{i_1} Y_{i_2} \ldots Y_{i_p}</tex> является правилом в <tex>G\Gamma'</tex> по построению <tex>G\Gamma'</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<br/tex>.Так как каждое из порождений <tex>Y_j Y_i \overset{*}underset{\underset{GGamma}{\Rightarrow}}w_j^*w_i</tex> содержит менее <tex>n</tex> шагов, к ним можно применить предположение индукции и заключить, что , если <tex>w_j w_i \ne \varepsilon</tex>, то <tex>Y_j Y_i \overset{*}underset{\underset{GGamma'}{\Rightarrow}}w_j^*w_i</tex>.<br/>Таким образом , <tex>A \underset{G\Gamma'}{\rightarrowRightarrow} Y_{i_1} Y_{i_2} X_1 X_2 ... X_k \oversetldots Y_{*i_p}{\underset{G\Gamma'}{\Rightarrow}} ^* w</tex>. Подставив <tex>S</tex> вместо <tex>A</tex> в утверждение (*), видим, что <tex>w \in L(\Gamma)</tex> для <tex>w \ne \varepsilon</tex> тогда и только тогда, когда <tex>w \in L(\Gamma')<br/tex>Ч.т.дТак как после выполнения шага 5 алгоритма в <tex>\Gamma'</tex> могло добавиться только пустое слово <tex>\varepsilon</tex>, то язык, задаваемый КС-грамматикой <tex>\Gamma'</tex>, совпадает с языком, задаваемым КС-грамматикой <tex>\Gamma</tex>.
}}
=== Время работы алгоритма ===
Рассмотрим грамматику <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|statement=Алгоритм корректен: O(n)</tex>. Однако алгоритм удаления <tex>\varepsilon</tex>-правил будет работать за <tex>LO(G\left| \Gamma \right|)=L</tex>, поскольку для каждого правила можно будет добавить только <tex>O(G'1)</tex>сочетаний нетерминалов. |proof=== Пример ===Рассмотрим грамматику:Подставив :<tex>S\rightarrow ABCd</tex> вместо :<tex>A\rightarrow a|\varepsilon</tex> в утверждении выше, видим, что :<tex>w B\in L(G)rightarrow AC</tex> для :<tex>w C\ne rightarrow c|\varepsilon</tex> тогда  В ней <tex>A</tex>, <tex>B</tex> и только тогда, когда <tex>w C</tex> являются <tex>\in L(G')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<br/tex> Очевидно, что # Удалим праила <tex>A\rightarrow \varepsilon </tex> и <tex>C\rightarrow \in L(G)varepsilon</tex> тогда и только тогда, когда  В результате мы получим новую грамматику без <tex>\varepsilon </tex>-правил: :<tex>S\in L(G')rightarrow Ad|ABd|ACd|ABCd|Bd|BCd|Cd|d</tex>.:<tex>A\rightarrow a<br/tex> Таким образом, :<tex>B\rightarrow A|AC|C</tex>:<tex>L(G)=L(G')C\rightarrow c</tex> == См. также ==* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]* [[Нормальная_форма_Хомского|Нормальная форма Хомского]] == Источники информации ==* ''Хопкрофт Д. , Мотвани Р., Ульман Д.'' '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — С. 273: ISBN 5-8459-0261-4 (рус.)}}* [http://en.wikipedia.org/wiki/Chomsky_normal_form Wikipedia — Chomsky normal form]
== Литература ==[[Категория: Теория формальных языков]]* Ахо Альфред, Джеффри Ульман. Теория Синтаксического Анализа, Перевода и Компиляции. Том 1.[[Категория: Контекстно-свободные грамматики]]* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.[[Категория: Нормальные формы КС-грамматик]]
1632
правки

Навигация