Бюрократы, editor, Администраторы
422
правки
Изменения
→Время работы для однозначной грамматики
|proof=
Ситуацию <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> можно включить в <tex>I_j</tex> только по правилам <tex>(1)</tex> (если последний символ <tex>\alpha</tex> — терминал) и <tex>(2)</tex> (если нетерминал). В первом случае результат очевиден. Во втором случае допустим, что <tex>[A \rightarrow \alpha'B \cdot \beta, i]</tex> включается в <tex>I_j</tex>, когда рассматриваются две различные ситуации <tex>[B \rightarrow \eta_1 \cdot, k_1]</tex> и <tex>[B \rightarrow \eta_2 \cdot, k_2]</tex>. Тогда ситуация <tex>[A \rightarrow \alpha' \cdot B\beta, i]</tex> должна оказаться одновременно в <tex>I_{k_1}</tex> и в <tex>I_{k_2}</tex>. Таким образом, получаем:
* <tex>\alpha' \Rightarrow^* a_{i+1} \ldots a_{k_1}</tex> и <tex>\alpha' \Rightarrow^* a_{i+1} \ldots a_{k_2}</tex>,* <tex>\eta_1 \Rightarrow^* a_{k_1+1} \ldots a_j</tex> и <tex>\eta_2 \Rightarrow^* a_{k_2+1} \ldots a_j</tex>.Следовательно* , <tex>\alpha' \eta_1 \Rightarrow^* a_{i+1} \ldots a_j</tex> и <tex>\alpha' \eta_2 \Rightarrow^* a_{i+1} \ldots a_j</tex>.<br/>Заметим, что <tex>S \Rightarrow^* \gamma A \delta \Rightarrow^* a_1 \ldots a_i A \delta \Rightarrow a_1 \ldots a_i \alpha' B \beta \delta</tex>. Предположим, что <tex>\beta \delta \Rightarrow^* w'</tex>(ведь в грамматике нет непорождающих нетерминалов). Тогда:* <tex>S \Rightarrow^* a_1 \ldots a_i \alpha' \eta_1 w'</tex> и аналогично <tex>S \Rightarrow^* a_1 \ldots a_i \alpha' \eta_2 w'</tex>.<br/>Таким образом, если <tex>k_1 \ne k_2</tex>, то подстрока <tex>a_{i+1} \ldots a_j</tex> выводится двумя различными способами из <tex>\alpha' \eta_1</tex> и <tex>\alpha' \eta_2</tex>(поскольку в первом случае <tex>\alpha' \Rightarrow^* a_{i+1} \ldots a_{k_1}</tex>, а во втором <tex>\alpha' \Rightarrow^* a_{i+1} \ldots a_{k_2}</tex>), то есть у строки <tex>a_1 \ldots a_jw'</tex> есть два различных вывода, что противоречит однозначности грамматики. Если же <tex>k_1 = k_2</tex>, то <tex>\eta_1 \ne \eta_2</tex>, что приводит к аналогичному противоречию.
}}
