Изменения

'''<tex>j</tex>-м '''списком ситуаций''' <tex>I_j</tex> для входной цепочки <tex>\omega = a_1 a_2 ... a_n</tex>, где <tex>0 \leqslant j \leqslant n</tex>, называется множество ситуаций <tex>\lbrace [A \rightarrow \alpha \cdot \beta , i] \mid \alpha \Rightarrow^* a_{i+1} ... a_j; \exists \gamma, \delta : S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_i \rbrace</tex>. То есть <tex>\gamma \alpha </tex> выводит часть <tex>\omega</tex> c первого по <tex>j</tex>-й символ.}} {{Лемма|statement = <tex>(\exists \alpha : [S \rightarrow \alpha \cdot, 0] \in I_n) \Leftrightarrow \omega \in L(G)</tex>.|proof = Поскольку <tex>S \Rightarrow^* \gamma S \delta</tex> (при <tex>\gamma = \delta = \varepsilon</tex>), из определения <tex>I_n</tex> получаем, что <tex>([S \rightarrow \alpha \cdot, 0] \in I_n) \Leftrightarrow (S \Rightarrow \alpha \Rightarrow^* a_1 ... a_n = \omega)</tex>.

'''Инициализация.<br/>Добавим новый стартовый вспомогательный нетерминал <tex>S'</tex> и правило <tex>S' \rightarrow S</tex>.<br>

'''ПродолжениеПостроение <tex>I_j</tex> по <tex>I_0,...,I_{j-1}</tex>.<br/>