Изменения

База: для любой ситуации из <tex>I_0</tex> (инициализация) <tex>\alpha = \varepsilon \Rightarrow^* \varepsilon </tex> и <tex>S' \Rightarrow^* \gamma A S \delta </tex> при <tex>\gamma = \delta = \varepsilon </tex>.<br/>

Тогда <tex>\alpha = \alpha' a_{j} , [A \rightarrow \alpha' \cdot a_{j} \beta, i] \in I_{j-1}</tex>. По и.п. предположению, <tex>\alpha' \Rightarrow^* a_{i+1}...a_{j-1} </tex> и существуют <tex>\gamma'</tex> и <tex>\delta' </tex> такие, что <tex>S' \Rightarrow^* \gamma' A \delta', \gamma' = \Rightarrow^* a_1...a_{i} </tex>. Значит , <tex> \alpha = \alpha' a_{j} \Rightarrow^* a_{i+1}...a_{j} </tex> и при <tex>\gamma = \gamma', \delta = \delta' </tex> для <tex>[A \rightarrow \alpha \cdot \beta, i]\in I_j</tex> утверждение верно.

Тогда <tex>\alpha = \alpha' B , [A \rightarrow \alpha' \cdot B \beta, k] \in I_{i}</tex> и <tex> [B \rightarrow \eta \cdot, i] \in I_{j} </tex>. По и.п. предположению, <tex>\alpha' \Rightarrow^* a_{k+1}...a_{i}, \eta \Rightarrow^* a_{i+1}...a_{j} </tex>, откуда <tex>\alpha = \alpha' B \Rightarrow^*a_{k+1}...a_{j} </tex>. Также по и.п. Кроме того, существуют <tex>\gamma'</tex> и <tex>\delta' </tex> такие, что <tex>S' \Rightarrow^* \gamma' A \delta', \gamma' = a_1...a_{k} </tex>. Значит , при <tex>\gamma = \gamma', \delta = \delta' </tex> для <tex>[A \rightarrow \alpha \cdot \beta, i]\in I_j</tex> утверждение верно.

Тогда <tex>\alpha = \varepsilon, i = j, [B \rightarrow \alpha' \cdot A \betaeta, k] \in I_{j}, A \Rightarrow \beta</tex>. По и.п. предположению <tex>\alpha' \Rightarrow^* a_{k+1}...a_{i}</tex> и существуют <tex>\gamma'</tex> и <tex>\delta' </tex> такие, что <tex>S' \Rightarrow^* \gamma' B \delta', \gamma' \Rightarrow^* a_1...a_{k} </tex>. Значит , при <tex>\gamma = \gamma' \alpha', \delta = \beta eta \delta' </tex> выполнено <tex> S' \Rightarrow^* \gamma A \delta</tex>, значит для следовательно <tex>[A \rightarrow \alpha \cdot \beta, i]\in I_j</tex> утверждение верно.