205
правок
Изменения
→Доказательство корректности алгоритма
== Доказательство корректности алгоритма ==
{{УтверждениеТеорема|statement= Если грамматика <tex>A \overset{*}{\underset{G'}{\Rightarrow}}w</tex> была построена с помощью описанного выше алгоритма по грамматике <tex>(A \ne S')G</tex> тогда и только тогда, когда то <tex>A \overset{*}{\underset{L(G') = L(G}{\Rightarrow}}w</tex> и <tex>w \ne ) - \varepsilon</tex>.
|proof=
Для этого достаточно доказать, что
<tex>A \overset{*}{\underset{G'}{\Rightarrow}}w</tex> <tex>(A \ne S')</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/>
