Изменения
→Корректность алгоритма
*Необходимость <br>
Докажем по индукции.<br>
База: для любой ситуации из <tex>I_0</tex> <tex>\alpha \Rightarrow^* \varepsilon </tex> и <tex>S \Rightarrow^* \gamma A \delta </tex> при <tex>\gamma = \varepsilon </tex>.<br>
Индукционный переход (и.п.): пусть верно для всех ситуаций из списков <tex> I_{i}, i \leqslant j </tex>. Пусть включаем <tex>[A \rightarrow \alpha \cdot \beta, i] </tex> в <tex>I_{j}</tex>. Рассмотрим три случая:<br>
*Пусть включаем по правилу 4<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' = 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]</tex> утверждение верно.
*Пусть включаем по правилу 5<br>
Тогда <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]</tex> утверждение верно.
Тогда <tex>\alpha = \varepsilon, i = j, [B \rightarrow \alpha' \cdot A \beta, k] \in I_{j}</tex>. По и.п. <tex>\alpha' \Rightarrow^* a_{k+1}...a_{i}</tex> и существуют <tex>\gamma'</tex> и <tex>\delta' </tex> такие, что <tex>S \Rightarrow^* \gamma' B \delta', \gamma' = a_1...a_{k} </tex>. Значит при <tex>\gamma = \gamma' \alpha', \delta = \beta \delta' </tex> выполнено <tex> S \Rightarrow^* \gamma A \delta</tex>, значит для <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> утверждение верно.
*Достаточность
Для всех наборов <tex>\tau = {\alpha, \beta, \gamma, \delta, A, i , j} </tex> нужно доказать, что если <tex> S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_{i}, A \rightarrow \alpha \beta \in P, \alpha \Rightarrow^* a_{i+1}...aa_{j}</tex>, то <tex> [A \rightarrow \alpha \cdot B \beta, i] \in I_{j}</tex>.<br>
*Рангом набора <tex> \tau </tex> называется <tex> \tau_{1}(\tau) + 2(j + \tau_{2}(\tau) + \tau_{3}(\tau))</tex>, где <tex>\tau_{1}(\tau)</tex> — длина кратчайшего вывода <tex>S \Rightarrow^* \gamma A \delta </tex>, <tex>\tau_{2}(\tau)</tex> — длина кратчайшего вывода <tex>\gamma \Rightarrow^* a_1...a_{i}</tex>, <tex>\tau_{3}(\tau)</tex> — длина кратчайшего вывода <tex>\alpha \Rightarrow^* a_{i+1}...a_{j}</tex>.
Докажем утверждение по индукции:<br>
База: если ранг <tex>\tau</tex> равен 0, то <tex>\tau_{1} = \tau_{2} = \tau_{3} = j = i = 0</tex>. Значит <tex>\alpha = \gamma = \delta = \varepsilon </tex>, <tex>A = S</tex>, следовательно <tex>S \rightarrow \beta \in P</tex>. Значит по правилу 1 <tex>[S \rightarrow \cdot \beta, 0] \in I_0</tex>
Индукционный переход:<br>
Пусть ранг <tex>\tau</tex> равен <tex>r > 0</tex>, пусть для всех наборов с меньшими рангами утверждение верно. Докажем для набора <tex>\tau</tex>. Для этого рассмотрим три случая:
*<tex>\alpha</tex> оканчивается терминалом<br>
