Изменения

# Перебираем правила грамматики <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{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>. Продолжаем, пока очередь не станет пустой.

|style="border-top:solid 2px gray" rowspan=2|Зададим начальные значения массивам <tex>\mathtt{counter}\ </tex> и <tex>\mathtt{isEpsilon}</tex>.

|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> остался без изменений.

# Для каждого правила вида <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>.