Изменения

:* Докажем, что если слово допускается автоматом, то его можно вывести в грамматике. Рассмотрим слово <tex> \alpha </tex> длины <tex> k </tex>. Рассмотрим какую-либо последовательность переходов автомата, допускающую данное слово <tex> \langle S,\alpha \rangle \vdash^k \langle ok,\varepsilon \rangle </tex>. Для каждого одношагового перехода в автомате существует соответствующее правило в грамматике. Значит для подпоследовательности переходов из <tex> k-1 </tex> шага <tex> \langle S, \alpha \rangle \vdash^{k-1} \langle U,c \rangle </tex> существует соответствующая последовательность применений правил <tex> S \Rightarrow^{k-1} \alpha c^{-1} U </tex>. Для последнего перехода в автомате <tex> \langle U,c \rangle \vdash \langle ok, \varepsilon \rangle </tex> существует правило <tex> U \Rightarrow c </tex>. Таким образом, существует последовательность применений правил грамматики, выводящая слово <tex> \alpha </tex>.

}}

== Источники информации ==