205
правок
Изменения
м
→Доказательство корректности алгоритма
|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>p = 1</tex><br/>
В этом случае в <tex>G'</tex> есть правило <tex>A \rightarrow w</tex>. Согласно конструкции <tex>G'</tex> в <tex>G</tex> есть правило <tex>A \rightarrow \alpha</tex>, причем <tex>\alpha-</tex> это <tex>w</tex>, символы которой, возможно, перемежаются <tex>\varepsilon-</tex> порождающими переменными. Тогда в <tex>G</tex> есть порождения <tex>A \underset{G}{\Rightarrow} \alpha \overset{*}{\underset{G}{\Rightarrow}}w</tex>, где на шагах после первого, из всех переменных в цепочке <tex>\alpha</tex> выводиться <tex>\varepsilon</tex>.<br/>
:'''Предположение'''. Пусть из <tex>[A \overset{*}{\underset{G'}{\Rightarrow}}w</tex> следует, что <tex>(A \ne S')]</tex> <tex>\Rightarrow [A \overset{*}{\underset{G}{\Rightarrow}}w</tex> и <tex>w \ne \varepsilon]</tex> верно для <tex>p < n</tex>.<br/>
:'''Переход'''. <tex>p = n</tex><br/>
Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G'}{\Rightarrow}X_1 X_2...X_k
:'''Базис'''. <tex>p = 1</tex><br/>
<tex>A \rightarrow w</tex> является правилом в <tex>G</tex>. Поскольку <tex>w \ne \varepsilon</tex>, эта же правило будет и в <tex>G'</tex>, поэтому <tex>A \overset{*}{\underset{G'}{\Rightarrow}}w</tex>.
:'''Предположение'''. Пусть из <tex>[A \overset{*}{\underset{G}{\Rightarrow}}w</tex> и <tex>w \ne \varepsilon] \Rightarrow [следует, что A \overset{*}{\underset{G'}{\Rightarrow}}w (A \ne S')]</tex> верно для <tex>p < n</tex>.<br/>
:'''Переход'''. <tex>p = n</tex><br/>
Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G}{\Rightarrow}Y_1 Y_2...Y_m
