317
правок
Изменения
Нет описания правки
|about=2
|statement=
Пусть <tex>G \gamma = (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>(*)</tex> каждая ситуация из каждого списка рассматривается по одному разу). Тогда ситуация <tex>[A \rightarrow \alpha' \cdot B\beta, i]</tex> должна оказаться одновременно в <tex>I_{k_1}</tex> и в <tex>I_{k_2}</tex>. Таким образом, получаем:
