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