205
правок
Изменения
м
→Доказательство корректности алгоритма
|proof =
Для этого достаточно доказать, что
<tex>A \overset{*}{\underset{G'}{\Rightarrow}}w</tex> тогда и только тогда, когда <tex>A \overset{*}{\underset{G}{\Rightarrow}}w</tex> и <tex>w \ne \varepsilon</tex>(*).
<tex>\Rightarrow)</tex><br\>
Пусть <tex>A \overset{*}{\underset{G'}{\Rightarrow}}w</tex>. Несомненно, <tex>w \ne \varepsilon</tex>, поскольку <tex>G'</tex> - грамматика без <tex>\varepsilon</tex>-правил и <tex>A \ne S'</tex>.<br/>Докажем индукцией по длине порождения, что <tex>A \overset{*}{\underset{G}{\Rightarrow}}w</tex>.<br/>
Обозначим длину порождения за <tex>p</tex>.
:<tex>A \underset {G}{\Rightarrow} Y_1 Y_2...Y_m \overset{*}{\underset{G}{\Rightarrow}} X_1 X_2...X_k \overset{*}{\underset{G}{\Rightarrow}} w_1 w_2...w_k = w</tex><br/>
Ч.т.д.<br/>
<tex>\Leftarrow)</tex><br/>
Пусть <tex>A \overset{*}{\underset{G}{\Rightarrow}}w</tex> и <tex>w \ne \varepsilon</tex>.<br/>
Докажем индукцией по длине порождения, что <tex>A \overset{*}{\underset{G'}{\Rightarrow}}w</tex>.<br/>
Ч.т.д.
Подставив <tex>S</tex> вместо <tex>A</tex> в утверждение(*), видим, что <tex>w \in L(G)</tex> для <tex>w \ne \varepsilon</tex> тогда и только тогда, когда <tex>w \in L(G')</tex>.
}}
