Бюрократы, editor, Администраторы
422
правки
Изменения
Нет описания правки
Построим список разбора для <tex>\omega</tex>
Строим <tex>I_0</tex><br>
<i>Шаг 1.</i> Если <tex>(S \rightarrow \alpha ) \in P</tex>, включить <tex>[S \rightarrow \cdot \alpha, 0]</tex> в <tex>I_0</tex>.<br>
Пока можно включить новые ситуации в <tex>I_0</tex> повторяем шаги 2 и 3.<br>
<i>Шаг 2.</i> Если <tex>[B \rightarrow \gamma \cdot, 0] \in I_0</tex>, включить в <tex>I_0</tex> ситуацию <tex>[A \rightarrow \alpha B \cdot \beta, 0]</tex> для всех <tex>[A \rightarrow \alpha \cdot B \beta, 0]</tex> из <tex>I_0</tex>.<br>
<i>Шаг 3.</i> Для всех <tex>[A \rightarrow \alpha \cdot B \beta, 0] \in I_0</tex>, для всех <tex>\gamma</tex> таких, что <tex>(B \rightarrow \gamma ) \in P</tex> включить <tex>[B \rightarrow \cdot \gamma, 0]</tex> в <tex>I_0</tex>.<br>
Построение <tex>I_j</tex> по <tex>I_0, I_1, ..., I_{j-1}</tex>. <br>
<i>Шаг 4.</i> Для каждой ситуации <tex>[B \rightarrow \alpha \cdot a_{j} \beta, i] \in I_{j-1}</tex>, где <tex>a_j</tex> — j-й символ в <tex>\omega</tex>, включить <tex>[B \rightarrow \alpha a_{j} \cdot \beta, i] </tex> в <tex>I_j</tex>.<br>
*<i>Рангом набора </i> <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>
Индукционный переход:
Пусть ранг <tex>\tau</tex> равен <tex>r > 0</tex>, пусть для всех наборов с меньшими рангами утверждение верно. Докажем для набора <tex>\tau</tex>. Для этого рассмотрим три случая:<br> <br>
<b>1. <tex>\alpha</tex> оканчивается терминалом </b> <br>
<tex>\alpha = \alpha' a</tex>. <tex>\alpha \Rightarrow^*a_{i+1}...a_{j}</tex>, значит <tex>a = a_{j}</tex>. Рассмотрим набор <tex>\tau' = \mathcal {f} \alpha', a_{j} \beta, \gamma, \delta, A, i, j-1 \mathcal {g} </tex>. <tex>(A \rightarrow \alpha' a_{j} \beta ) \in P</tex>, следовательно ранг <tex>\tau'</tex> равен <tex>r - 2</tex>, так как <tex>\tau_{1}(\tau) = \tau_1(\tau'), \tau_2(\tau) = \tau_2(\tau'), \tau_{3}(\tau) = \tau_3(\tau')</tex>. Значит по и.п. <tex>[A \rightarrow \alpha' \cdot a_{j} \beta, i] \in I_{j-1}</tex>, по правилу 4 получаем, что <tex>[A \rightarrow \alpha \cdot \beta, i] </tex> будет добавлена в <tex>I_{j}</tex>. <br> <br>
<b> 2. <tex>\alpha</tex> оканчивается нетерминалом </b><br>
<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} \alpha', B \beta, \gamma, \delta, A, i, k \mathcal {g} </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} \eta, \varepsilon, \gamma \alpha', \beta \delta, B, k, j \mathcal {g} </tex>. <tex>S \Rightarrow^* \gamma A \delta \Rightarrow \gamma \alpha' B \beta \delta</tex>, следовательно <tex>\tau_1(\tau'') \leqslant \tau_1(\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_3(\tau) = n_1 + n_2</tex>. Так как <tex> B \Rightarrow \eta \Rightarrow^* a_{k+1}...a_{j}</tex>, то <tex>\tau_3(\tau'') = n_2 - 1</tex>. Очевидно, что <tex>\tau_2(\tau'') = \tau_2(\tau) + n_1</tex>. Тогда ранг <tex>\tau''</tex> равен <tex>\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)</tex> <tex>= \tau_1(\tau) - 1 + 2(\tau_2(\tau) + \tau_3(\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> по правилу 4 или 5 <tex>[A \rightarrow \alpha \cdot \beta, i] </tex> будет добавлена в <tex>I_{j}</tex>. <br> <br>
