Изменения

Тогда <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 \eta, 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 = \eta \delta' </tex> выполнено <tex> S' \Rightarrow^* \gamma A \delta</tex>, следовательно <tex>[A \rightarrow \alpha \cdot \beta, i] \in I_j</tex>.

Для всех наборов <tex>\tau = {\langle \alpha, \beta, \gamma, \delta, A, i , j} \rangle</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 \beta, i] \in </tex> в <tex> I_{j}</tex>.

''Рангом набора'' <tex> \tau </tex> называется <tex> \tau_{1S'}(\tau) + 2(j + \tau_{2\gamma}(\tau) + \tau_{3\alpha}(\tau))</tex>, где <tex>\tau_{1S'}(\tau)</tex> — длина кратчайшего вывода <tex>S' \Rightarrow^* \gamma A \delta </tex>, <tex>\tau_{2\gamma}(\tau)</tex> — длина кратчайшего вывода <tex>\gamma \Rightarrow^* a_1...a_{i}</tex>, <tex>\tau_{3\alpha}(\tau)</tex> — длина кратчайшего вывода <tex>\alpha \Rightarrow^* a_{i+1}...a_{j}</tex>.

Докажем утверждение индукцией по индукциирангу набора.<br/>База: если ранг <tex>\tau</tex> равен 0, то <tex>\tau_{1S'} = \tau_{2\gamma} = \tau_{3\alpha} = j = i = 0</tex>. Значит , <tex>A = S'</tex>, <tex>\alpha = \gamma = \delta = \varepsilon </tex>, <tex>A = S', \beta = S </tex>. Значит по При инициализации такая ситуация <tex>[S' \rightarrow \cdot S, 0] \in </tex> будет добавлена в <tex>I_0</tex>.<br/>

<tex>\alpha = \alpha' ac</tex>. <tex>\alpha \Rightarrow^*a_{i+1}...a_{j}</tex>, значит <tex>a c = a_{j}</tex>. Рассмотрим набор <tex>\tau' = \mathcal {f} langle \alpha', a_{j} \beta, \gamma, \delta, A, i, j-1 \mathcal {g} rangle </tex>. <tex>(A \rightarrow \alpha' a_{j} \beta) \in P</tex>, следовательно ранг <tex>\tau'</tex> равен <tex>r - 2</tex>, так как <tex>\tau_{1S'}(\tau) = \tau_1tau_{S'}(\tau'), \tau_2tau_{\gamma}(\tau) = \tau_2tau_{\gamma}(\tau'), \tau_{3\alpha}(\tau) = \tau_3tau_{\alpha}(\tau')</tex>. Значит , по и.п. предположению <tex>[A \rightarrow \alpha' \cdot a_{j} \beta, i] \in I_{j-1}</tex>, по правилу 1 получаем, что и <tex>[A \rightarrow \alpha \cdot \beta, i] </tex> будет добавлена в <tex>I_{j}</tex>по правилу 1.

<tex>\alpha = \alpha' B</tex>. <tex>\alpha \Rightarrow^*a_{i+1}...a_{j}</tex>, значит <tex>\mathcal {9} k</tex> такое, что <tex>\alpha' \Rightarrow^*a_{i+1}...a_{k}, B \Rightarrow^* a_{k+1}...a_{j}</tex>.<br/> Рассмотрим набор <tex>\tau' = \mathcal {f} langle \alpha', B \beta, \gamma, \delta, A, i, k \mathcal {g} rangle</tex>, его ранг меньше <tex>r</tex>. По и.п. , следовательно <tex>[A \rightarrow \alpha' \cdot B \beta, i] \in I_{k}</tex>по предположению. <br/>Пусть <tex>B \Rightarrow \eta</tex> — первый шаг в кратчайшем выводе <tex>B \Rightarrow^* a_{k+1}...a_{j}</tex>. Рассмотрим набор <tex>\tau'' = \mathcal {f} langle \eta, \varepsilon, \gamma \alpha', \beta \delta, B, k, j \mathcal {g} rangle</tex>. <tex>S \Rightarrow^* \gamma A \delta \Rightarrow \gamma \alpha' B \beta \delta</tex>, следовательно <tex>\tau_1tau_{S'}(\tau'') \leqslant \tau_1tau_{S'}(\tau) + 1</tex>.<br> Обозначим длину Пусть длина кратчайшего вывода <tex>\alpha' \Rightarrow^*a_{i+1}...a_{k}</tex> за равна <tex>n_1</tex>, а длину длина кратчайшего вывода <tex> B \Rightarrow^* a_{k+1}...a_{j}</tex> за равна <tex>n_2</tex>. Тогда <tex>\tau_3tau_{\alpha}(\tau) = n_1 + n_2</tex>. Так как <tex> B \Rightarrow \eta \Rightarrow^* a_{k+1}...a_{j}</tex>, то <tex>\tau_3tau_{\alpha}(\tau'') = n_2 - 1</tex>. Очевидно, что <tex>\tau_2tau_{\gamma}(\tau'') = \tau_2tau_{\gamma}(\tau) + n_1</tex>. Тогда ранг <tex>\tau''</tex> равен <tex>\tau_1tau_{S'}(\tau'') + 2(\tau_2tau_{\gamma}(\tau'') + \tau_3tau_{\alpha}(\tau'') + j) \leqslant \tau_1tau_{S'}(\tau) + 1 + 2(\tau_2tau_{\gamma}(\tau) + n_1 + n_2 - 1 + j)</tex> <tex>= \tau_1tau_{S'}(\tau) - 1 + 2(\tau_2tau_{\gamma}(\tau) + \tau_3tau_{\alpha}(\tau) + j) < r</tex>. Значит , по и.п. предположению для <tex>\tau''</tex>, <tex>[B \rightarrow \eta \cdot, k] \in I_{j}</tex>. Из того, что <tex>[A \rightarrow \alpha' \cdot B \beta, i] \in I_{k}</tex> и <tex>[B \rightarrow \eta \cdot, k] \in I_{j}</tex> , по правилу 1 или 2 <tex>[A \rightarrow \alpha \cdot \beta, i] </tex> будет добавлена в <tex>I_{j}</tex>.

3. <tex>\alpha= \varepsilon</tex> является пустой.<br/><tex>\alpha = \varepsilon</tex>, значит В этом случае <tex>i = j, \tau_3tau_{\alpha}(\tau) = 0, (A \rightarrow \beta ) \in P</tex>.<br/> Если <tex> \tau_1tau_{S'}(\tau) = \neq 0</tex>, то т.к. иначе <tex> \gamma = \varepsilon</tex>, следовательно <tex> \tau_2tau_{\gamma}(\tau) = 0, i = 0 </tex>, откуда <tex> r = 0</tex>, а по и.п. но <tex>r > 0</tex>. Значит Т.к. <tex> \tau_1tau_{S'}(\tau) \neq > 0</tex>. Тогда , <tex> \mathcal {9} exists B, \gamma', \gamma'', \delta', \delta''</tex> такие, что <tex>: S' \Rightarrow^* \gamma' B \delta' \Rightarrow \gamma' \gamma'' A \delta' \delta''</tex>, где <tex>(B = \rightarrow \gamma'' A \delta'' ) \in P</tex>. Рассмотрим набор <tex>\tau' = \mathcal {f} langle \gamma'', A \delta'', \gamma', \delta', B, k, j \mathcal {g} rangle</tex>, где <tex>k</tex> такое, что <tex>\gamma' \Rightarrow^* a_1...a_{k}, \gamma'' \Rightarrow^* a_{k+1}...a_{j}</tex>. Обозначим длину Пусть длина кратчайшего вывода <tex>\gamma' \Rightarrow^*a_{1}...a_{k}</tex> за равна <tex>n_1</tex>, а длину длина кратчайшего вывода <tex> \gamma'' \Rightarrow^* a_{k+1}...a_{j}</tex> за равна <tex>n_2</tex>. <br/>Найдем ранг <tex>\tau'</tex>. <tex>\tau_1tau_{S'}(\tau') = \tau_1tau_{S'}(\tau) - 1, \tau_2tau_{\gamma}(\tau') = n_1, \tau_3tau_{\alpha}(\tau') = n_2, </tex>. <tex>\tau_{\tau_3alpha}(\tau) = 0, \tau_2tau_{\gamma}(\tau) = n_1 + n_2</tex>. Следовательно , следовательно ранг <tex>\tau'</tex> равен <tex>r - 1</tex>. Значит , по и.п. предположению <tex>[B \rightarrow \gamma'' \cdot A \delta'', k] \in I_{j}</tex>, следовательно по правилу 3 <tex>[A \rightarrow \cdot \beta, i] </tex> будет добавлена в <tex>I_{j}</tex>.