Изменения

'''Алгоритм Эрли''' позволяет определить, выводится ли данное слово <tex>\omegaw</tex> в данной [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободной]] грамматике <tex>G</tex>.

'''Вход:''' КС грамматика <tex> G=\langle N,\Sigma, P, S \rangle</tex> и слово <tex>\omegaw</tex>.<br/>'''Выход:''' <tex>true</tex>, если <tex>\omegaw</tex> выводится в <tex>G</tex>; <tex>false</tex> — иначе.

Пусть <tex>G = (N, \Sigma, P, S)</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная]] грамматика и <tex>\omega w = a_1 a_2 ... a_n</tex> {{---}} входная цепочка из <tex>\Sigma^*</tex>.Объект вида <tex>[A \rightarrow \alpha \cdot \beta, i]</tex>, где <tex>A \rightarrow \alpha \beta </tex> — правило из <tex>P</tex> и <tex>0 \leqslant i \leqslant n</tex> — позиция в <tex>\omegaw</tex>, называется '''ситуацией''', относящейся к цепочке <tex>\omegaw</tex>.

'''<tex>j</tex>-м списком ситуаций''' <tex>I_j</tex> для входной цепочки <tex>\omega w = a_1 a_2 ... a_n</tex>, где <tex>0 \leqslant j \leqslant n</tex>, называется множество ситуаций <tex>\lbrace [A \rightarrow \alpha \cdot \beta , i] \mid \alpha \Rightarrow^* a_{i+1} ... a_j; \exists \gamma, \delta : S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_i \rbrace</tex>. То есть <tex>\gamma \alpha </tex> выводит часть <tex>\omegaw</tex> c первого по <tex>j</tex>-й символ.

|statement = <tex>(\exists \alpha : [S \rightarrow \alpha \cdot, 0] \in I_n) \Leftrightarrow \omega w \in L(G)</tex>.|proof = Поскольку <tex>S \Rightarrow^* \gamma S \delta</tex> (при <tex>\gamma = \delta = \varepsilon</tex>), из определения <tex>I_n</tex> получаем, что <tex>([S \rightarrow \alpha \cdot, 0] \in I_n) \Leftrightarrow (S \Rightarrow \alpha \Rightarrow^* a_1 ... a_n = \omegaw)</tex>.

Последовательность списков ситуаций <tex>I_0, I_1, .., I_n</tex> называется <b>списком разбора</b> для входной цепочки <tex>\omegaw</tex>.

Построим список разбора для <tex>\omegaw</tex> с помощью данного алгоритма и воспользуемся леммой, доказанной выше.<br>

Построим список разбора для строки <tex>\omega w = (a + a)</tex> в грамматике со следующими правилами:

Так как <tex>[S' \rightarrow S \cdot , 0] \in I_5</tex>, то <tex>\omega w \in L(G) </tex>.<br>