Изменения

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

|definition = Правила вида <tex>A \to \varepsilon</tex> называются '''<tex>\varepsilon</tex>-правилами''' (англ. ''<tex>\varepsilon</tex>-rule'').

|definition = Назовем Нетерминал <tex>A</tex> называется '''<tex>\varepsilon</tex>-порождающим''' (англ. ''<tex>\varepsilon</tex>-generating''), если <tex>A \Rightarrow^* \varepsilon</tex>.}} == Алгоритм поиска &epsilon;-порождающих нетерминалов =='''Вход:''' КС-грамматику грамматика <tex>G\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. === Доказательство корректности ==={{Теорема|statement = Описанный выше алгоритм находит все <tex>\varepsilon</tex>-порождающие нетерминалы грамматики <tex>\Gamma<br/tex>.|proof = :(1) Для доказательства корректности алгоритма достаточно показать, что, если множество <tex>P\varepsilon</tex> -порождающих нетерминалов на очередной итерации алгоритма не содержит изменялось, то алгоритм нашел все <tex>\varepsilon</tex>-правилпорождающие нетерминалы. Пусть после завершения алгоритма существуют нетерминалы такие, либо :(2) есть точно одно что они являются <tex>\varepsilon</tex>-порождающими, но не были найдены алгоритмом. Выберем из этих нетерминалов нетерминал <tex>B</tex>, из которого выводится <tex>\varepsilon</tex> за наименьшее число шагов. Тогда в грамматике есть правило <tex>S B \to rightarrow C_1C_2 \ldots C_k</tex>, где каждый нетерминал <tex>C_i</tex> {{---}} <tex>\varepsilon</tex> и -порождающий. Каждый <tex>SC_i</tex> не встречается входит в правых частях остальных правил множество <tex>\varepsilon</tex>-порождающих нетерминалов, так как иначе вместо <tex>B</tex> необходимо было взять <tex>C_i</tex>. Следовательно, на одной из итераций алгоритма <tex>B</tex>Pуже добавился в множество <tex>\varepsilon</tex>-порождающих нетерминалов. Противоречие. Следовательно, алгоритм находит все <tex>\varepsilon</tex>-порождающие нетерминалы.

По данной произвольной КС-грамматике === Модификация с очередью ===Заведем несколько структур:*<tex>G\mathtt{isEpsilon[nonterm_i]} \ </tex> часто бывает удобно строить новую КС{{---грамматику }} для каждого нетерминала будем хранить пометку, является он <tex>G'\varepsilon</tex> без -порождающим или нет.*<tex>\varepsilonmathtt{concernedRules[nonterm_i]} \ </tex>{{---}} для каждого нетерминала будем хранить список номеров тех правил, эквивалентную исходной.в правой части которых он встречается;==Алгоритм удаления &epsilon;-правил==:''Вход''. КС-грамматика *<tex>\mathtt{counter[rule_i]} \ </tex> {{---}} для каждого правила будем хранить счетчик количества нетерминалов в правой части, которые еще не помечены <tex> G=(N,\Sigma, P, S)varepsilon</tex>.-порождающими;:''Выход''. Эквивалентная КС-грамматика *<tex> G'=(N',\Sigma, P', S') mathtt{Q} \ </tex> без {{---}} очередь нетерминалов, помеченных <tex>\varepsilon</tex>-правилпорождающими, но еще не обработанных.:''Метод''. (1) Построить <Сначала проставим <tex>N_e=\mathtt{A \mid A \in Nfalse}</tex> и в <tex>A \Rightarrow_{G}^mathtt{*isEpsilon}\varepsilon\}</tex>. (2) Построить для всех нетерминалов, а в <tex>P'\mathtt{counter} \ </tex> так: Если для каждого правила запишем количество нетерминалов справа от него. Те правила, для которых <tex>A \rightarrow mathtt{counter} \alpha_0 B_1 \alpha_1 B_2 </tex> сразу же оказался нулевым, добавим в <tex>\alpha_2 ... B_k \alpha_k \in P, k \geqslant 0mathtt{Q}</tex> и объявим истинным соответствующий <tex>B_i \in N_emathtt{isEpsilon}</tex> для , так как это <tex>1 \leqslant i \leqslant k<varepsilon</tex>-правила. Теперь будем доставать из очереди по одному нетерминалу, но ни один символ в цепочках смотреть на список <tex>a_j (0 \leqslant j \leqslant k) mathtt{concernedRules} \notin N_e</tex>, то включить в для него и уменьшать <tex>P'\mathtt{counter}</tex> все правила вида для всех правил оттуда. Если <tex>A \rightarrow \alpha_0 X_1 mathtt{counter} \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 \varepsilonmathtt{Q}</tex> (это могло бы произойти . Продолжаем, пока очередь не станет пустой. === Время работы алгоритма === в случае, если все Базовый алгоритм работает за <tex>O(\left| \Gamma \alpha_iright| ^ 2)</tex> равны <tex>\varepsilon. В алгоритме с модификацией нетерминал попадает в очередь ровно один раз, соответственно ровно один раз мы пройдемся по списку правил, в правой части которых он лежит. Суммарно получается </tex>). O(3\left| \Gamma \right|) Если <tex>S \in N_e</tex>, включить в . === Пример ===Рассмотрим грамматику, причем сразу пронумеруем правила:#<tex>P'S\rightarrow ABC</tex> правила #<tex>S' \rightarrow \varepsilon \mid SDS </tex> где #<tex>S'-A\rightarrow \varepsilon</tex> новый символ, и положить #<tex>N'=N B\cup \{ S' \}rightarrow AC</tex>. В противном случае положить #<tex>N'=NC\rightarrow \varepsilon</tex> и #<tex>S'=SD\rightarrow d</tex>. (4) Положить <tex> G'=(N'Поскольку правило 6 содержит справа терминалы,\Sigmaоно заведомо не будет влиять на ответ, Pпоэтому мы не будем его учитывать.', S') Построим массив списков </tex>. <tex>\Box\mathtt{concernedRules}</tex>Для доказательства корректности нам понадобиться следующее утверждение:.{{Утверждение| class="wikitable"|statementcolspan= 5 |<tex>A \oversetmathtt{*concernedRules}{\underset{G'}{\Rightarrow}}w</tex> |-!<tex>(A \ne S')</tex>&nbsp; тогда и только тогда, когда !<tex>A \overset{*}{\underset{G}{\Rightarrow}}w</tex>&nbsp; и&nbsp; !<tex>w \ne \varepsilonB</tex>|proof=!<tex>\RightarrowC</tex>!<br\tex>Пусть D</tex>A \overset{*|-|2|1, 4|1|1, 4|2|} {| class="wikitable" style="border:solid 2px gray"!style="border-right:solid 2px gray"|<tex>\undersetmathtt{G'Q}{\Rightarrow}}w</tex>. Несомненно, !style="border-right:solid 2px gray" colspan=5| <tex>w \ne \varepsilonmathtt{isEpsilon}</tex>, поскольку !style="border-right:solid 2px gray" colspan=5| <tex>G'\mathtt{counter}</tex> !Комментарий|- грамматика без !style="border-top:solid 2px gray; border-right:solid 2px gray" rowspan=2|<tex>\varepsilonleft \{ \right \}</tex>!style="border-правил и top:solid 2px gray"|<tex>A \ne S'</tex>.<br/>Докажем индукцией по длине порождения, что !style="border-top:solid 2px gray"|<tex>A \overset{*}{\underset{G}{\Rightarrow}}w</tex>.!style="border-top:solid 2px gray"|<tex>B<br/tex> Обозначим длину порождения за !style="border-top:solid 2px gray"|<tex>pC</tex>.!style="border-top:'''Базис'''. solid 2px gray; border-right:solid 2px gray"|<tex>p = 1D</tex><br/>В этом случае в <tex>G'</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 \rightarrow wmathtt{counter} \ </tex>. Согласно конструкции и <tex>G'\mathtt{isEpsilon}</tex> в <tex>G</tex> есть правило <tex>A \rightarrow \alpha</tex>, причем <tex>\alpha.|-</tex> это <tex>w</tex>, символы которой, возможно, перемежаются <tex>\varepsilon|0|0|0|0|style="border-right:solid 2px gray"|0|3|2|0|2|style="border-</tex> порождающими переменными. Тогда в right:solid 2px gray"|0|-|style="border-top:solid 2px gray; border-right:solid 2px gray" rowspan=2|<tex>G\left \{A,C \right \}</tex> есть порождения !style="border-top:solid 2px gray"|<tex>A \underset{G}{\Rightarrow} \alpha \overset{*}{\underset{G}{\Rightarrow}}wS</tex>, где на шагах после первого, из всех переменных в цепочке !style="border-top:solid 2px gray"|<tex>\alphaA</tex> выводиться !style="border-top:solid 2px gray"|<tex>\varepsilonB</tex>.!style="border-top:solid 2px gray"|<tex>C<br/tex>!style="border-top:'''Предположение'''. Пусть solid 2px gray; border-right:solid 2px gray"|<tex>[A \overset{*}{\underset{G'}{\Rightarrow}}wD</tex> <tex>(A \ne S')]</tex>&nbsp; <!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>\Rightarrow [A \overset{*}{varepsilon</tex>-правилами. Пометим левые нетерминалы из этих правил и добавим их в очередь. После этого в <tex>\undersetmathtt{GQ}{\Rightarrow}}w</tex>&nbsp; и&nbsp; лежит <tex>w \ne \varepsilon]<A</tex> верно для и <tex>p < nC</tex>.<br/>:'''Переход'''. , а <tex>p = n\mathtt{counter} \ </tex><br/>остался без изменений.|-|0Пусть в порождении <tex>n</tex> шагов, <tex>n > |1|0|1</tex>. Тогда оно имеет вид <tex>A\underset{G'}{\Rightarrow}X_1 X_2...X_k\overset{*}{\underset{G'}{\Rightarrow}}w</tex>, где |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>X_i \in N left\{C \cup right\Sigma }</tex>. Первое использованное правило должно быть построено по правилу !style="border-top:solid 2px gray"|<tex>A \rightarrow Y_1 Y_2...Y_mS</tex>, где цепочка !style="border-top:solid 2px gray"|<tex>Y_1 Y_2...Y_mA</tex> совпадает с цепочкой !style="border-top:solid 2px gray"|<tex>X_1 X_2...X_kB</tex>, цепочка !style="border-top:solid 2px gray"|<tex>Y_1 Y_2...Y_mC</tex>, возможно, перемежаются !style="border-top:solid 2px gray; border-right:solid 2px gray"|<tex>\varepsilon-D</tex> порождающими переменными.<br/>Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2...w_k</!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>X_i \overset{*}{\underset{G'}{\Rightarrow}}w_i</tex>, декрементируем те счетчики, которые относятся к связанным с ним правилам. К очереди ничего не добавится. Если <tex>X_i</tex> есть терминал, то <tex>w |-|0|1|0|1|style= X_i</tex>, a если переменная, то порождение "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>X_i \overset{*}left\{B \underset{G'}{right\Rightarrow}}w_i</tex> содержит менее !style="border-top:solid 2px gray"|<tex>nS</tex> шагов.!style="border-top:solid 2px gray"|<br/tex> По предположению <A</tex>X_i \overset{*}{\underset{G}{\Rightarrow}}w_i!style="border-top:solid 2px gray"|</tex>.B<br/tex>Теперь построим соответствующее порождение в !style="border-top:solid 2px gray"|<tex>GC</tex>.!style="border-top:solid 2px gray; border-right:solid 2px gray"|<tex>D<br/tex>!style="border-top:<tex>A \underset {G}{\Rightarrow} Y_1 Y_2...Y_m \overset{*}{\underset{G}{\Rightarrow}} X_1 X_2.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>.X_k \overset{|-|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;-правил из грамматики =='''Вход:''' КС-грамматика <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>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>\Gamma'</tex> была построена с помощью описанного выше алгоритма по грамматике <tex>\Gamma</tex>, то <tex>L(\Gamma') = L(\Gamma)</tex>.|proof =Сначала докажем, что, если не выполнять шаг 5 алгоритма, то получится грамматика <tex>\Gamma' : L(\Gamma') = L(\Gamma) \setminus \lbrace \varepsilon \rbrace </tex>.<br/>Для этого достаточно доказать, что<tex>A \underset{\Gamma'}{\Rightarrow}^*}{\underset{G}{\Rightarrow}} w_1 w_2..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>.w_k = w</tex><br/>Ч.т.д.<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>.

Теперь можно доказать корректность:{{Утверждение|statement=Алгоритм корректен: В результате мы получим новую грамматику без <tex>L(G)=L(G')\varepsilon</tex>-правил: |proof=Подставив :<tex>S\rightarrow Ad|ABd|ACd|ABCd|Bd|BCd|Cd|d</tex> вместо :<tex>A</tex> в утверждении выше, видим, что <tex>w \in L(G)rightarrow a</tex> для :<tex>w B\ne \varepsilonrightarrow A|AC|C</tex> тогда и только тогда, когда :<tex>w C\in L(G')rightarrow c</tex> == См.<br/> Очевиднотакже ==* [[Контекстно-свободные_грамматики, что <tex>\varepsilon \in L(G)</tex> тогда и только тогда_вывод, когда <tex>\varepsilon \in L(G')</tex>.<br/> Таким образом_лево-_и_правосторонний_вывод, <tex>L(G)=L(G')</tex>. _дерево_разбора|Контекстно-свободные грамматики]]* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]}}== Литература Источники информации ==* Ахо Альфред, Джеффри Ульман''Хопкрофт Д. Теория Синтаксического Анализа, Перевода и КомпиляцииМотвани Р. Том 1.* Джон Хопкрофт, Раджив Мотвани, Джеффри УльманД. '' '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002.— С. 273: ISBN 5-8459-0261-4 (рус.)* [http://en.wikipedia.org/wiki/Chomsky_normal_form Wikipedia — Chomsky normal form] [[Категория: Теория формальных языков]][[Категория: Контекстно-свободные грамматики]][[Категория: Нормальные формы КС-грамматик]]