Изменения

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

|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>-правил (или неукорачивающей)порождающим''', если <tex>P</tex> не содержит <tex>\varepsilon</tex>-правил или есть точно одно <tex>\varepsilon</tex>-правило <tex>S \to \varepsilon</tex> и <tex>S</tex> не встречается в правых частях остальных правил из <tex>P</tex>(англ.}}{{Определение|definition = Нетерминал <tex>A</tex> называется '''<tex>\varepsilon</tex>-порождающим'generating''), если <tex>A \Rightarrow^* \varepsilon</tex>.

== Алгоритм удаления &epsilon;-правил из грамматики ===== Поиск поиска &epsilon;-порождающих нетерминалов ==='''Вход:'''. КС -грамматика <tex> G\Gamma=\langle N,\Sigma, P, S \rangle</tex>.<br/>'''Выход:'''. Множество множество <tex>\varepsilon</tex>-порождающих нетерминалов.<br/>''Схема алгоритма:''# Если Найти все <tex>A \rightarrow \varepsilon</tex> — правило -правила. Составить множество, состоящее из нетерминалов, входящих в левые части таких правил.# Перебираем правила грамматики <tex>G</tex>, то <tex>A</tex> — <tex>\varepsilonGamma</tex>-порождающий нетерминал.# Если найдено правило <tex>B A \rightarrow C_1C_2...\ldots C_k</tex> — правило грамматики <tex>G</tex>, где для которого верно, что каждый <tex>C_i</tex> — принадлежит множеству, то добавить <tex>\varepsilonA</tex>-порождающий нетерминалв множество.# Если на шаге 2 множество изменилось, то <tex>B</tex> — <tex>\varepsilon</tex>-порождающий нетерминалповторить шаг 2.

|statement = Нетерминал <tex>A</tex> является Описанный выше алгоритм находит все <tex>\varepsilon</tex>-порождающим тогда и только тогда, когда вышеприведенный алгоритм идентифицирует <tex>A</tex> как порождающие нетерминалы грамматики <tex>\varepsilonGamma</tex>-порождающий.|proof = Индукция по длине кратчайшего порождения <tex>A \Rightarrow^* \varepsilon</tex>:''База.'' Для доказательства корректности алгоритма достаточно показать, что, если множество <tex>A \Rightarrow^* \varepsilon</tex> за один шаг-порождающих нетерминалов на очередной итерации алгоритма не изменялось, то есть <tex>A \rightarrow\varepsilon</tex>. алгоритм нашел все <tex>\varepsilon</tex>-порождающий нетерминал <tex>A</tex> обнаруживается алгоритмом согласно первому пункту алгоритмапорождающие нетерминалы.

:''Индукция.'' Пусть после завершения алгоритма существуют нетерминалы такие, что они являются <tex>A \Rightarrow^* \varepsilon</tex> за -порождающими, но не были найдены алгоритмом. Выберем из этих нетерминалов нетерминал <tex>B</tex>, из которого выводится <tex>n\varepsilon</tex> за наименьшее число шагов. Тогда первых шаг порождения в грамматике есть правило <tex>A B \rightarrow C_1C_2...\ldots C_k</tex>, где каждый нетерминал <tex>C_i \Rightarrow^* \varepsilon</tex> за менее, чем {{---}} <tex>n\varepsilon</tex> шагов-порождающий. По индукционному предположению каждый нетерминал Каждый <tex>C_i</tex> обнаруживается как входит в множество <tex>\varepsilon</tex>-порождающийпорождающих нетерминалов, так как иначе вместо <tex>B</tex> необходимо было взять <tex>C_i</tex>. Тогда нетерминал Следовательно, на одной из итераций алгоритма <tex>B</tex> уже добавился в множество <tex>A\varepsilon</tex> обнаружиться вторым пунктом алгоритма как -порождающих нетерминалов. Противоречие. Следовательно, алгоритм находит все <tex>\varepsilon</tex>-порождающийпорождающие нетерминалы.

=== Схема алгоритма удаления &epsilonМодификация с очередью ===Заведем несколько структур:*<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> G!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>\langle Nvarepsilon</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\Sigma}</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>, Pдекрементируем те счетчики, которые относятся к связанным с ним правилам. К очереди ничего не добавится.|-|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 \rangleright\}</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> G'=\langle Nlbrace A,C \Sigma, P'rbrace</tex>.# Добавим <tex>B</tex> в множество, так как правая часть правила <tex>B\rightarrow AC</tex> состоит только из нетерминалов из множества.# Повторим второй пункт для правила <tex>S \rangle : L(G) rightarrow ABC</tex> и получим множество <tex>\setminus \mathcal {f} \varepsilon lbrace A, B, C, S \mathcal {g} = L(G')rbrace</tex>.# Больше нет нерассмотренных правил, содержащих справа только нетерминалы из множества.

''Схема алгоритма:''# Найти все Таким образом <tex>\varepsilon</tex>-порождаюшие нетерминалы.# Удалить все <tex>\varepsilon</tex>-правила из <tex>P</tex>.# Рассмотрим правила вида (*) порождающими нетерминалами являются <tex>A \rightarrow \alpha_0 B_1 \alpha_1 B_2 \alpha_2 ... B_k \alpha_k</tex>, где <tex>\alpha_iB</tex> — последовательности из терминалов и нетерминалов, <tex>B_jC</tex> — <tex>\varepsilonи </tex>-порождающие нетерминалы. Добавить все возможные правила вида (*), в которых либо присутствует, либо отсутствует <tex>B_j\; (1 \le j \le k)</tex>, кроме правила <tex>A \rightarrow \varepsilon</tex>. Такое правило может возникнуть, если все <tex>\alpha_i = \varepsilonS</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>P</tex> в исходной грамматике <tex>GP'</tex>.# Найти все <tex>\varepsilon</tex> есть правило -порождаюшие нетерминалы.# Для каждого правила вида <tex>S A \rightarrow \varepsilonalpha_0 B_1 \alpha_1 B_2 \alpha_2 \ldots B_k \alpha_k \ </tex> (где <tex>\alpha_i</tex> — последовательности из терминалов и нетерминалов, <tex>SB_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\Gamma'</tex> была построена с помощью описанного выше алгоритма по грамматике <tex>G\Gamma</tex>, то <tex>L(G\Gamma') = L(G\Gamma) - \varepsilon</tex>.

<tex>A \overset{*}underset{\underset{GGamma'}{\Rightarrow}}^*w</tex> тогда и только тогда, когда <tex>A \overset{*}underset{\underset{GGamma}{\Rightarrow}}^*w</tex> и <tex>w \ne \varepsilon</tex> (*).

<tex>\Rightarrow)</tex><br\>Пусть <tex>A \overset{*}underset{\underset{GGamma'}{\Rightarrow}}^*w</tex>. Несомненно, &nbsp; и&nbsp; <tex>w \ne \varepsilon</tex>, поскольку <tex>G'.<br/tex> - грамматика без Докажем индукцией по длине порождения в грамматике <tex>\varepsilonGamma'</tex>-правил.<br/>Докажем индукцией по длине порождения, что <tex>A \overset{*}underset{\underset{GGamma}{\Rightarrow}}^*w</tex>.<br/> Обозначим длину порождения за <tex>p</tex>.:'''БазисБаза'''. <tex>p = 1A \underset{\Gamma'}{\Rightarrow} w</tex>.<br/>В этом случае в <tex>G\Gamma'</tex> есть правило <tex>A \rightarrow w</tex>. Согласно конструкции По построению <tex>G\Gamma'</tex> в <tex>G\Gamma</tex> есть правило <tex>A \rightarrow \alpha</tex>, причем <tex>\alpha-</tex> это — цепочка <tex>w</tex>, символы элементы которой, возможно, перемежаются <tex>\varepsilon-</tex> -порождающими нетерминалами. Тогда в <tex>G\Gamma</tex> есть порождения <tex>A \underset{G\Gamma}{\Rightarrow} \alpha \overset{*}underset{\underset{GGamma}{\Rightarrow}}^*w</tex>, где на шагах после первого, из всех нетерминалов в цепочке <tex>\alpha</tex> выводиться <tex>\varepsilon</tex>.<br/>:'''Предположениеиндукции'''. Пусть из <tex>A \overset{*}underset{\underset{GGamma'}{\Rightarrow}}^*w\ne \varepsilon</tex> менее, чем за <tex>n</tex> шагов, следует, что <tex>A \overset{*}underset{\underset{GGamma}{\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\Gamma'}{\Rightarrow}X_1 X_2...\ldots X_k\overset{*}underset{\underset{GGamma'}{\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>Y_1 Y_2...Y_m</tex>символы которой, возможно, перемежаются <tex>\varepsilon-</tex> -порождающими нетерминалами.<br/>Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2...\ldots w_k</tex>, где <tex>X_i \overset{*}underset{\underset{GGamma'}{\Rightarrow}}^*w_i</tex>. Если <tex>X_i</tex> есть — терминал, то <tex>w_i = X_i</tex>, a если нетерминал, то порождение <tex>X_i \overset{*}underset{\underset{GGamma'}{\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 {GGamma}{\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{G}{\Rightarrow}}ww_i</tex>&nbsp; и&nbsp; <tex>w \ne \varepsilon</tex>.<br/> Докажем индукцией по длине порождения, что значит <tex>A \overset{*}{\underset{G'}{\Rightarrow}}w</tex>.<br/> Обозначим длину порождения за <tex>p</tex>.<br/>:'''Базис'''. <tex>p = 1</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 \overset{*}{\underset{G}{\Rightarrow}}w</tex> и <tex>w \ne \varepsilon следует, что A \overset{*}{\underset{G'}{\Rightarrow}}w </tex> верно для <tex>p < n</tex>.<br/>:'''Переход'''. <tex>p = n</tex><br/>Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{GGamma}{\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...w_m</tex>, где <tex>Y_i \overset{^*}{\underset{G'}{\Rightarrow}}w_i</tex>.<br/>Пусть <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...ldots 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'Gamma}{\Rightarrow}}w_j</tex>.<br/>Таким образом <tex>A \underset{G'}{\rightarrow} X_1 X_2 ... X_k \overset{^*}{w_1 w_2 \underset{G'}{\Rightarrow}} ldots w_k = w</tex>.<br/>Ч.т.д.

<tex>\Leftarrow</tex><br/>Пусть <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>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 \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}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>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>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/>Таким образом, <tex>A \underset{\Gamma'}{\Rightarrow} Y_{i_1} Y_{i_2} \ldots Y_{i_p} \underset{\Gamma'}{\Rightarrow}^* w</tex>. Подставив <tex>S</tex> вместо <tex>A</tex> в утверждение (*), видим, что <tex>w \in L(G\Gamma)</tex> для <tex>w \ne \varepsilon</tex> тогда и только тогда, когда <tex>w \in L(G\Gamma')</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| = 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> == См. также ==* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]* [[Нормальная_форма_Хомского|Нормальная форма Хомского]] == Источники информации ==