Изменения
→Корректность алгоритма
==Корректность алгоритма==
{{Теорема
|statement = <tex>[A \rightarrow \alpha \cdot \beta, i] \in I_{j} \Leftrightarrow \alpha \Rightarrow^* a_{i+1}...a_{j}</tex> и <tex> \mathcal {9} \gamma </tex> и <tex> \delta</tex> такие, что <tex>S \Rightarrow^* \gamma A \delta</tex> и <tex> \gamma \Rightarrow^* a_1...a_{i}</tex>.
|proof =
<tex>\Leftarrow</tex><br>
Для всех наборов <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}...a_{j}</tex>, то <tex> [A \rightarrow \alpha \cdot B \beta, i] \in I_{j}</tex>.<br>
*<bi>Рангом набора </bi> <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>
