|
[math]\Rightarrow[/math]
Докажем по индукции.
База: для любой ситуации из [math]I_0[/math] [math]\alpha \Rightarrow^* \varepsilon [/math] и [math]S' \Rightarrow^* \gamma A \delta [/math] при [math]\gamma = \varepsilon [/math].
Индукционный переход (и.п.): пусть верно для всех ситуаций из списков [math] I_{i}, i \leqslant j [/math]. Пусть включаем [math][A \rightarrow \alpha \cdot \beta, i] [/math] в [math]I_{j}[/math]. Рассмотрим три случая:
1. Пусть включаем по правилу 1
Тогда [math]\alpha = \alpha' a_{j} , [A \rightarrow \alpha' \cdot a_{j} \beta, i] \in I_{j-1}[/math]. По и.п. [math]\alpha' \Rightarrow^* a_{i+1}...a_{j-1} [/math] и существуют [math]\gamma'[/math] и [math]\delta' [/math] такие, что [math]S' \Rightarrow^* \gamma' A \delta', \gamma' = a_1...a_{i} [/math]. Значит [math] \alpha = \alpha' a_{j} \Rightarrow^* a_{i+1}...a_{j} [/math] и при [math]\gamma = \gamma', \delta = \delta' [/math] для [math][A \rightarrow \alpha \cdot \beta, i][/math] утверждение верно.
2. Пусть включаем по правилу 2
Тогда [math]\alpha = \alpha' B , [A \rightarrow \alpha' \cdot B \beta, k] \in I_{i}[/math] и [math] [B \rightarrow \eta \cdot, i] \in I_{j} [/math]. По и.п. [math]\alpha' \Rightarrow^* a_{k+1}...a_{i}, \eta \Rightarrow^* a_{i+1}...a_{j} [/math], откуда [math]\alpha = \alpha' B \Rightarrow^*a_{k+1}...a_{j} [/math]. Также по и.п. существуют [math]\gamma'[/math] и [math]\delta' [/math] такие, что [math]S' \Rightarrow^* \gamma' A \delta', \gamma' = a_1...a_{k} [/math]. Значит при [math]\gamma = \gamma', \delta = \delta' [/math] для [math][A \rightarrow \alpha \cdot \beta, i][/math] утверждение верно.
3. Пусть включаем по правилу 3
Тогда [math]\alpha = \varepsilon, i = j, [B \rightarrow \alpha' \cdot A \beta, k] \in I_{j}[/math]. По и.п. [math]\alpha' \Rightarrow^* a_{k+1}...a_{i}[/math] и существуют [math]\gamma'[/math] и [math]\delta' [/math] такие, что [math]S' \Rightarrow^* \gamma' B \delta', \gamma' \Rightarrow^* a_1...a_{k} [/math]. Значит при [math]\gamma = \gamma' \alpha', \delta = \beta \delta' [/math] выполнено [math] S' \Rightarrow^* \gamma A \delta[/math], значит для [math][A \rightarrow \alpha \cdot \beta, i][/math] утверждение верно.
[math]\Leftarrow[/math]
Для всех наборов [math]\tau = {\alpha, \beta, \gamma, \delta, A, i , j} [/math] нужно доказать, что если [math] S' \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_{i}, A \rightarrow \alpha \beta \in P, \alpha \Rightarrow^* a_{i+1}...a_{j}[/math], то [math] [A \rightarrow \alpha \cdot \beta, i] \in I_{j}[/math].
- Рангом набора [math] \tau [/math] называется [math] \tau_{1}(\tau) + 2(j + \tau_{2}(\tau) + \tau_{3}(\tau))[/math], где [math]\tau_{1}(\tau)[/math] — длина кратчайшего вывода [math]S' \Rightarrow^* \gamma A \delta [/math], [math]\tau_{2}(\tau)[/math] — длина кратчайшего вывода [math]\gamma \Rightarrow^* a_1...a_{i}[/math], [math]\tau_{3}(\tau)[/math] — длина кратчайшего вывода [math]\alpha \Rightarrow^* a_{i+1}...a_{j}[/math].
Докажем утверждение по индукции:
База: если ранг [math]\tau[/math] равен 0, то [math]\tau_{1} = \tau_{2} = \tau_{3} = j = i = 0[/math]. Значит [math]\alpha = \gamma = \delta = \varepsilon [/math], [math]A = S', \beta = S [/math]. Значит по инициализации [math][S' \rightarrow \cdot S, 0] \in I_0[/math].
Индукционный переход:
Пусть ранг [math]\tau[/math] равен [math]r \gt 0[/math], пусть для всех наборов с меньшими рангами утверждение верно. Докажем для набора [math]\tau[/math]. Для этого рассмотрим три случая:
1. [math]\alpha[/math] оканчивается терминалом
[math]\alpha = \alpha' a[/math]. [math]\alpha \Rightarrow^*a_{i+1}...a_{j}[/math], значит [math]a = a_{j}[/math]. Рассмотрим набор [math]\tau' = \mathcal {f} \alpha', a_{j} \beta, \gamma, \delta, A, i, j-1 \mathcal {g} [/math]. [math](A \rightarrow \alpha' a_{j} \beta) \in P[/math], следовательно ранг [math]\tau'[/math] равен [math]r - 2[/math], так как [math]\tau_{1}(\tau) = \tau_1(\tau'), \tau_2(\tau) = \tau_2(\tau'), \tau_{3}(\tau) = \tau_3(\tau')[/math]. Значит по и.п. [math][A \rightarrow \alpha' \cdot a_{j} \beta, i] \in I_{j-1}[/math], по правилу 1 получаем, что [math][A \rightarrow \alpha \cdot \beta, i] [/math] будет добавлена в [math]I_{j}[/math].
2. [math]\alpha[/math] оканчивается нетерминалом
[math]\alpha = \alpha' B[/math]. [math]\alpha \Rightarrow^*a_{i+1}...a_{j}[/math], значит [math]\mathcal {9} k[/math] такое, что [math]\alpha' \Rightarrow^*a_{i+1}...a_{k}, B \Rightarrow^* a_{k+1}...a_{j}[/math].
Рассмотрим набор [math]\tau' = \mathcal {f} \alpha', B \beta, \gamma, \delta, A, i, k \mathcal {g} [/math], его ранг меньше [math]r[/math]. По и.п. [math][A \rightarrow \alpha' \cdot B \beta, i] \in I_{k}[/math].
Пусть [math]B \Rightarrow \eta[/math] — первый шаг в кратчайшем выводе [math]B \Rightarrow^* a_{k+1}...a_{j}[/math]. Рассмотрим набор [math]\tau'' = \mathcal {f} \eta, \varepsilon, \gamma \alpha', \beta \delta, B, k, j \mathcal {g} [/math]. [math]S \Rightarrow^* \gamma A \delta \Rightarrow \gamma \alpha' B \beta \delta[/math], следовательно [math]\tau_1(\tau'') \leqslant \tau_1(\tau) + 1[/math].
Обозначим длину кратчайшего вывода [math]\alpha' \Rightarrow^*a_{i+1}...a_{k}[/math] за [math]n_1[/math], а длину кратчайшего вывода [math] B \Rightarrow^* a_{k+1}...a_{j}[/math] за [math]n_2[/math]. Тогда [math]\tau_3(\tau) = n_1 + n_2[/math]. Так как [math] B \Rightarrow \eta \Rightarrow^* a_{k+1}...a_{j}[/math], то [math]\tau_3(\tau'') = n_2 - 1[/math]. Очевидно, что [math]\tau_2(\tau'') = \tau_2(\tau) + n_1[/math]. Тогда ранг [math]\tau''[/math] равен [math]\tau_1(\tau'') + 2(\tau_2(\tau'') + \tau_3(\tau'') + j) \leqslant \tau_1(\tau) + 1 + 2(\tau_2(\tau) + n_1 + n_2 - 1 + j)[/math] [math]= \tau_1(\tau) - 1 + 2(\tau_2(\tau) + \tau_3(\tau) + j) \lt r[/math]. Значит по и.п. для [math]\tau''[/math], [math][B \rightarrow \eta \cdot, k] \in I_{j}[/math]. Из того, что [math][A \rightarrow \alpha' \cdot B \beta, i] \in I_{k}[/math] и [math][B \rightarrow \eta \cdot, k] \in I_{j}[/math] по правилу 1 или 2 [math][A \rightarrow \alpha \cdot \beta, i] [/math] будет добавлена в [math]I_{j}[/math].
3. [math]\alpha[/math] является пустой
[math]\alpha = \varepsilon[/math], значит [math]i = j, \tau_3(\tau) = 0[/math].
Если [math] \tau_1(\tau) = 0[/math], то [math] \gamma = \varepsilon[/math], следовательно [math] \tau_2(\tau) = 0, i = 0 [/math], откуда [math] r = 0[/math], а по и.п. [math]r \gt 0[/math]. Значит [math] \tau_1(\tau) \neq 0[/math]. Тогда [math] \mathcal {9} B, \gamma', \gamma'', \delta', \delta''[/math] такие, что [math]S' \Rightarrow^* \gamma' B \delta' \Rightarrow \gamma' \gamma'' A \delta' \delta''[/math], где [math]B = \gamma'' A \delta'' \in P[/math]. Рассмотрим набор [math]\tau' = \mathcal {f} \gamma'', A \delta'', \gamma', \delta', B, k, j \mathcal {g} [/math], где [math]k[/math] такое, что [math]\gamma' \Rightarrow^* a_1...a_{k}, \gamma'' \Rightarrow^* a_{k+1}...a_{j}[/math]. Обозначим длину кратчайшего вывода [math]\gamma' \Rightarrow^*a_{1}...a_{k}[/math] за [math]n_1[/math], а длину кратчайшего вывода [math] \gamma'' \Rightarrow^* a_{k+1}...a_{j}[/math] за [math]n_2[/math].
Найдем ранг [math]\tau'[/math]. [math]\tau_1(\tau') = \tau_1(\tau) - 1, \tau_2(\tau') = n_1, \tau_3(\tau') = n_2, \tau_3(\tau) = 0, \tau_2(\tau) = n_1 + n_2[/math]. Следовательно ранг [math]\tau'[/math] равен [math]r - 1[/math]. Значит по и.п. [math][B \rightarrow \gamma'' \cdot A \delta'', k] \in I_{j}[/math], следовательно по правилу 3 [math][A \rightarrow \cdot \beta, i] [/math] будет добавлена в [math]I_{j}[/math]. |
