Изменения
Нет описания правки
Если <tex>[S \rightarrow \alpha \cdot, 0] \in I_n</tex>, то <tex>\omega \in L(G) </tex>.<br>
==Корректность алгоритма=={{Теорема|statement = <tex>[A \rightarrow \alpha \cdot \beta, i] \in I_{j} \Leftrightarrow \alpha \Rightarrow^* a_{i+1}...a_{j}</tex> и <tex> \mathcal {9} \gamma </tex> и <tex> \delta</tex> такие, что <tex>S \Rightarrow^* \gamma A \delta</tex> и <tex> \gamma \Rightarrow^* a_1...a_{i}</tex>|proof =*Необходимость <br>Докажем по индукции.<br>База: для любой ситуации из <tex>I_0</tex> <tex>\alpha \Rightarrow^* \varepsilon </tex> и <tex>S \Rightarrow^* \gamma A \delta </tex> при <tex>\gamma = \varepsilon </tex>.<br>Индукционный переход (и.п.): пусть верно для всех ситуаций из списков <tex> I_{i}, i \leqslant j </tex>. Пусть включаем <tex>[A \rightarrow \alpha \cdot \beta, i] </tex> в <tex>I_{j}</tex>. Рассмотрим три случая:<br>*Пусть включаем по правилу 4<br>Тогда <tex>\alpha = \alpha' a_{j} , [A \rightarrow \alpha' \cdot a_{j} \beta, i] \in I_{j-1}</tex>. По и.п. <tex>\alpha' \Rightarrow^* a_{i+1}...a_{j-1} </tex>и существуют <tex>\gamma'</tex> и <tex>\delta' </tex> такие, что <tex>S \Rightarrow^* \gamma' A \delta', \gamma' = a_1...a_{i} </tex>. Значит <tex> \alpha = \alpha' a_{j} \Rightarrow^* a_{i+1}...a_{j}</tex> и при <tex>\gamma = \gamma', \delta = \delta' </tex> для <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> утверждение верно.*Пусть включаем по правилу 5<br>Тогда <tex>\alpha = \alpha' B , [A \rightarrow \alpha' \cdot B \beta, k] \in I_{i}</tex> и <tex> [B \rightarrow \eta \cdot, i] \in I_{j} </tex>. По и.п. <tex>\alpha' \Rightarrow^* a_{k+1}...a_{i}, \eta \Rightarrow^* a_{i+1}...a_{j} </tex>, откуда <tex>\alpha = \alpha' B \Rightarrow^*a_{k+1}...a_{j} </tex>. Также по и.п. существуют <tex>\gamma'</tex> и <tex>\delta' </tex> такие, что <tex>S \Rightarrow^* \gamma' A \delta', \gamma' = a_1...a_{k} </tex>. Значит при <tex>\gamma = \gamma', \delta = \delta' </tex> для <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> утверждение верно.*Пусть включаем по правилу 6<br>Тогда <tex>\alpha = \varepsilon, i = j, [B \rightarrow \alpha' \cdot A \beta, k] \in I_{j}</tex>. По и.п. <tex>\alpha' \Rightarrow^* a_{k+1}...a_{i}</tex> и существуют <tex>\gamma'</tex> и <tex>\delta' </tex> такие, что <tex>S \Rightarrow^* \gamma' B \delta', \gamma' = a_1...a_{k} </tex>. Значит при <tex>\gamma = \gamma' \alpha', \delta = \beta \delta' </tex> выполнено <tex> S \Rightarrow^* \gamma A \delta</tex>, значит для <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> утверждение верно.}}
==Литература==
*А.Ахо, Дж. Ульман. Теория синтакcического анализа, перевода и компиляции. Том 1. Синтакcический анализ.
