Бюрократы, editor, Администраторы
422
правки
Изменения
Доказательство второго пункта леммы
|about=2
|statement=
Пусть <tex>G = (N, \Sigma, P, S)</tex> {{---}} однозначная КС-грамматика без непорождающих нетерминалов и <tex>a_1 \dots a_n</tex> {{---}} цепочка из <tex>\Sigma^*</tex>. Тогда алгоритм Эрли пытается включить <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> в <tex>I_j</tex> не более одного раза, если <tex>\alpha \ne \varepsilon</tex>.
|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>k_1 \ne k_2</tex>. Тогда существуют такие <tex>\gamma_1, \delta_1, \gamma_2</tex> и <tex>\delta_2</tex>, что <tex>S \Rightarrow^* \gamma_1 A \delta_1 \Rightarrow \gamma_1 \alpha' B \beta \delta_1</tex> и <tex>S \Rightarrow^* \gamma_2 A \delta_2 \Rightarrow \gamma_2 \alpha' B \beta \delta_2</tex>. Но в первом выводе <tex>\gamma_1 \alpha' \Rightarrow^* a_1 \dots a_{k_1}</tex>, а во втором <tex>\gamma_2 \alpha' \Rightarrow^* a_1 \dots a_{k_2}</tex>. Тогда для цепочки <tex>a_1 \dots a_n</tex> существуют два разных дерева вывода, в которых <tex>a_{i+1} \dots a_j</tex> выводится из <tex>\alpha' B</tex> двумя разными способами.
# Пусть <tex>k_1 = k_2= k</tex>. Тогда <tex>\eta_1 \ne \eta_2</tex>. Тогда, так как <tex>[B \rightarrow \eta_1 \cdot, k_1k] \in I_j</tex> и <tex>[B \rightarrow \eta_2 \cdot, k_1k] \in I_j</tex>, то <tex>\eta_1 \Rightarrow^* a_{k_1 k + 1} \dots a_j</tex> и <tex>\eta_2 \Rightarrow^* a_{k_1 + 1} \dots a_j</tex>, то есть <tex>a_{k_1 k + 1} \dots a_j</tex> выводится двумя разными способами. Так как <tex>[A \rightarrow \alpha' \cdot B \beta, i] \in I_{k_1}I_k</tex>, то <tex>S \Rightarrow^* \gamma A \delta \Rightarrow \gamma \alpha' B \beta \delta \Rightarrow^* a_1 \ldots a_i \alpha' B \beta \delta \Rightarrow^* a_1 \ldots a_i a_{i+1} a_k B \beta \delta \Rightarrow^* a_1 \ldots a_{k_1} B a_k \eta_1 \beta \delta</tex> и . Аналогично, <tex> S \Rightarrow^* a_1 \ldots a_{k_1} B a_k \eta_2 \beta \delta \Rightarrow a_1 \ldots a_i a_{i+1} \ldots a_{k_1} \eta </tex>. Теперь, если предположить, что <tex>\beta \delta \Rightarrow^* a_1 \ldots a_i a_{i+1} \ldots a_{k_1} a_{k_1+1} \ldots a_j w'</tex>, где то можно видеть, что <tex>S \Rightarrow^* a_1 \eta = ldots a_k \eta_1w'</tex> или и <tex>S \Rightarrow^* a_1 \eta = ldots a_k \eta_2w'</tex>, а поскольку, как мы установили, из <tex>w'\eta_1</tex> {{---}} некоторая строка, такая что и <tex>\beta \delta \Rightarrow^* w'eta_2</tex>. Таким образом, строка выводится <tex>a_1 \ldots a_i a_{ik +1} \ldots a_{k_1} a_{k_1+1} dots a_j</tex>, у строки <tex>a_1 \ldots a_j w'</tex> выводится двумя способамив данной грамматике есть два различных вывода, что противоречит однозначности.
}}
