Изменения

Удалим из входной грамматики Будем рассматривать грамматику [[Удаление eps-правил из грамматики|<tex>\varepsilon</tex>без &epsilon;-правилаправил]] и [[Удаление бесполезных символов из грамматики|бесполезные символыбесполезных символов]]. В итоге получится грамматика <tex>G = (N, \Sigma, P, S)</tex>.

<tex>I_0</tex> = <tex>\{[S ' \rightarrow \cdot \alphaS, 0] \, | \, S \rightarrow \alpha \in P\}</tex> # Правило (0) — инициализация

В циклах, помеченных <tex>(*)</tex> и <tex>(**)</tex> , просматривается не весь список <tex>I_j</tex>, а только те ситуации, которые еще не были просмотреныдобавлены на предыдущей итерации цикла <code>while</code>. Данная модификация является корректной.# Рассмотрим цикл <tex>(*)</tex>. Если в текущей ситуации <tex>[B \rightarrow \eta \cdot, i]</tex> этого цикла <tex>i \ne j</tex>, то во внутреннем цикле просматривается список с меньшим индексом, в который новые ситуации больше не добавляются. Поэтому после первого просмотра этого списка будут добавлены все ситуации, удовлетворяющие условию, и больше ситуацию <tex>[B \rightarrow \eta \cdot, i]</tex> в цикле <tex>(*)</tex> рассматривать не нужно. Если же <tex>i = j</tex>, то <tex>\eta \Rightarrow^* \varepsilon</tex>, что возможно, только если <tex>B = S \, ', \eta = \varepsilon</tex>. Тогда во внутреннем цикле не будет добавлено ни одной ситуации, так как <tex>S'</tex> не встречается в правых частях правил.

Таким образом, во все списки будут добавлены ситуации, которые были бы добавлены в ходе обычного алгоритма. Очевидно, что лишних ситуаций добавлено не будет, так как в циклах <tex>(*)</tex> и <tex>(**)</tex> просматривается подмножество полного списка. Значит два этих алгоритма эквивалентныэтот алгоритм эквивалентен оригинальному.