Изменения

# Перебираем правила грамматики <tex>\Gamma</tex>. Если найдено правило <tex>A \rightarrow C_1C_2...\ldots C_k</tex>, для которого верно, что каждый <tex>C_i</tex> принадлежит множеству, то добавить <tex>A</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>-порождающие нетерминалы.

*<tex>\mathtt{is\text{-}epsilonisEpsilon[nonterm_i]}\ </tex> {{---}} для каждого нетерминала будем хранить пометку, является он <tex>\varepsilon</tex>-порождающим или нет.*<tex>\mathtt{concerned\text{-}rulesconcernedRules[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{isisEpsilon} \text{-}epsilon}</tex> для всех нетерминалов, а в <tex>\mathtt{counter}\ </tex> для каждого правила запишем количество нетерминалов справа от него. Те правила, для которых <tex>\mathtt{counter}\ </tex> сразу же оказался нулевым, добавим в <tex>\mathtt{Q}</tex> и объявим истинным соответствующий <tex>\mathtt{is\text{-}epsilonisEpsilon}</tex>, так как это <tex>\varepsilon</tex>-правила. Теперь будем доставать из очереди по одному нетерминалу, смотреть на список <tex>\mathtt{concernedconcernedRules} \text{-}rules}</tex> для него и уменьшать <tex>\mathtt{counter}</tex> для всех правил оттуда. Если <tex>\mathtt{counter}\ </tex> какого-то правила в этот момент обнулился, то нетерминал из левой части этого правила помечается <tex>\varepsilon</tex>-порождающим, если еще не был помечен до этого, и добавляется в <tex>\mathtt{Q}</tex>. Продолжаем, пока очередь не станет пустой.

|Построим массив списков <tex>\mathtt{concerned\text{-}rules}</tex>.{| class="wikitable"| colspan=5 |<tex>\mathtt{concerned\text{-}rulesconcernedRules}</tex>

!style="border-top:solid 2px gray; border-right:solid 2px gray" rowspan=2|Зададим начальные значения массивам <tex>\mathttleft \{counter\right \}</tex> и !style="border-top:solid 2px gray"|<tex>S</tex>\mathtt{is\text{!style="border-}epsilon}top:solid 2px gray"|<tex>A</tex>.{| class!style="wikitableborder-top:solid 2px gray"|<tex>B</tex>|colspan!style=5 "border-top:solid 2px gray"| <tex>\mathtt{counter}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|}{| classstyle="wikitableborder-right:solid 2px gray" |colspan=5 | <tex>\mathtt{is\text{-}epsilon}</tex>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> остался без изменений.

|02|style="border-right:solid 2px gray"|0|}

|Заметим, что правила 3 и 5 являются style="border-top:solid 2px gray; border-right:solid 2px gray" rowspan=2|<tex>\varepsilon</tex>-правилами. Пометим левые нетерминалы из этих правил и добавим их в очередь. После этого в <tex>left\mathtt{Q}</tex> лежит <tex>A</tex> и <tex>C</tex>. <tex>\mathtt{counter}</tex> остался без изменений, а <tex>\mathtt{isright\text{-}epsilon}</tex> выглядит следующим образом:{| class!style="wikitableborder-top:solid 2px gray" |colspan=5 | <tex>\mathtt{is\text{-}epsilon}S</tex>!style="border-top:solid 2px gray"|-!<tex>SA</tex>!style="border-top:solid 2px gray"|<tex>AB</tex>!style="border-top:solid 2px gray"|<tex>BC</tex>!style="border-top:solid 2px gray; border-right:solid 2px gray"|<tex>CD</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>DA</tex>, декрементируем те счетчики, которые относятся к связанным с ним правилам. К очереди ничего не добавится.

|0|}|style="border-|Достанем из очереди <tex>A</tex>, декрементируем те счетчики, которые относятся к связанным с ним правилам. К очереди ничего не добавится, а <tex>\mathtt{counter}</tex> станет такимright:{| class="wikitablesolid 2px gray"|colspan=5 | <tex>\mathtt{counter}</tex>|-!1!2!3!4!5|-0

|style="border-right:solid 2px gray"|0|}

|Достанем из очереди style="border-top:solid 2px gray; border-right:solid 2px gray" rowspan=2|<tex>C\left\{B \right\}</tex>. После проведения действий из алгоритма в очередь добавится !style="border-top:solid 2px gray"|<tex>BS</tex>.{!style="border-top:solid 2px gray"| class<tex>A</tex>!style="wikitableborder-top:solid 2px gray"|<tex>B</tex>|colspan!style=5 "border-top:solid 2px gray"| <tex>\mathtt{counter}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|}{| classstyle="wikitableborder-right:solid 2px gray" |colspan=5 | <tex>\mathtt{is\text{-}epsilon}</tex>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>.

|0|}1|-|Достанем из очереди <tex>B</tex>. После действий алгоритма в очередь добавится S.{| classstyle="wikitableborder-right:solid 2px gray"|colspan=5 | <tex>\mathtt{counter}</tex>|-!1!2!3!4!5|-0

|0|}{| classstyle="wikitableborder-right:solid 2px gray" |colspan=5 | <tex>\mathtt{is\text{-}epsilon}</tex>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>.

|}|style="border-right:solid 2px gray"|Достанем из очереди <tex>S</tex>. Ничего не добавится в очередь и она останется пустой. Алгоритм закончил свое выполнение. Итого в множество <tex>\varepsilon</tex>-правил входят все нетерминалы, кроме <tex>D</tex>.0

# Для каждого правила вида <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>\Rightarrow</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>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>A \underset{\Gamma'}{\Rightarrow} Y_{i_1} Y_{i_2} ... \ldots Y_{i_p} \underset{\Gamma'}{\Rightarrow}^* w</tex>.

* [http://en.wikipedia.org/wiki/Chomsky_normal_form Wikipedia — Chomsky normal form]