205
правок
Изменения
м
→Доказательство корректности алгоритма
Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G}{\Rightarrow}Y_1 Y_2...Y_m
\overset{*}{\underset{G}{\Rightarrow}}w</tex>, где <tex>Y_i \in N \cup \Sigma </tex>. Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2...w_m</tex>, где <tex>Y_i \overset{*}{\underset{G'}{\Rightarrow}}w_i</tex>.<br/>
Пусть <tex>X_1, X_2, ... X_k</tex> будут теми из <tex>Y_j</tex>(в порядке записи), для которых <tex>w_i \ne \varepsilon</tex>. <tex>k \ge 1</tex>, поскольку <tex>w \ne \varepsilon</tex>.<br/> Таким образом <tex>A \rightarrow X_1 X_2 ... X_k</tex> является правилом в <tex>G'</tex> по построению <tex>G'</tex>.
Утверждаем, что <tex> X_1 X_2...X_k \overset{*}{\underset{G}{\Rightarrow}}w</tex>, поскольку только <tex>Y_j</tex>, которых нет среди <tex>X_1, X_2, ... X_k</tex>, использованы для порождения <tex>\varepsilon</tex> и не вносят ничего в порождение <tex>w</tex>.
Так как каждое из порождений <tex>Y_j \overset{*}{\underset{G}{\Rightarrow}}w_j</tex> содержит менее <tex>n</tex> шагов, к ним можно применить предположение индукции и заключить, что если <tex>w_j \ne \varepsilon</tex>, то <tex>Y_j \overset{*}{\underset{G'}{\Rightarrow}}w_j</tex>.<br/>
