Изменения

Пусть <tex>G = \langle N, \Sigma, P, S \rangle</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная]] грамматика и <tex>w = a_1 a_2 w_1 w_2 ... a_nw_n</tex> {{---}} входная цепочка из <tex>\Sigma^*</tex>.Объект вида <tex>[A \rightarrow \alpha \cdot \beta, i]</tex>, где <tex>A \rightarrow \alpha \beta </tex> — правило из <tex>P</tex> и <tex>0 \leqslant i \leqslant n</tex> — позиция в <tex>w</tex>, называется '''ситуацией''', относящейся к цепочке <tex>w</tex>. '''<tex> \cdot </tex>''' {{---}} вспомогательный символ, который не явлется терминалом или нетерминалом ( <tex> \cdot \notin \Sigma \cup N</tex>).

'''<tex>j</tex>-м списком ситуаций''' <tex>I_jD_j</tex> для входной цепочки <tex>w = a_1 a_2 w_1 w_2 ... a_nw_n</tex>, где <tex>0 \leqslant j \leqslant n</tex>, называется множество ситуаций <tex>\lbrace [A \rightarrow \alpha \cdot \beta , i] \mid \alpha \Rightarrow^* a_w_{i+1} ... a_jw_j; \exists \gamma, \delta : S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1w_1...a_i w_i \rbrace</tex>. То есть <tex>\gamma \alpha </tex> выводит часть <tex>w</tex> c первого по <tex>j</tex>-й символ.

|statement = <tex>(\exists \alpha : [S \rightarrow \alpha \cdot, 0] \in I_nD_n) \Leftrightarrow w \in L(G)</tex>.|proof = Поскольку <tex>S \Rightarrow^* \gamma S \delta</tex> (при <tex>\gamma = \delta = \varepsilon</tex>), из определения <tex>I_nD_n</tex> получаем, что <tex>([S \rightarrow \alpha \cdot, 0] \in I_nD_n) \Leftrightarrow (S \Rightarrow \alpha \Rightarrow^* a_1 w_1 ... a_n w_n = w)</tex>.

Последовательность списков ситуаций <tex>I_0D_0, I_1D_1, .., I_nD_n</tex> называется <b>списком разбора</b> для входной цепочки <tex>w</tex>.