editor
143
правки
Изменения
Нет описания правки
Множество языков, задаваемых праволинейными грамматиками, совпадает со множеством языков, задаваемых конечными автоматами.
|proof=
Пусть имеется конечный автомат. Построим для него праволинейную грамматику. Множеством нетерминалов нашей грамматики будет множество состояний автомата. Для каждой пары состояний автомата <tex>A</tex> и <tex>B</tex> такой, что имеется переход из <tex>A</tex> в <tex>B</tex> по символу <tex>c</tex>, добавим в грамматику правило <tex> A \to cB </tex>. Затем для каждой пары состояний автомата <tex>A</tex> и <tex>B</tex> такой, что имеется переход из <tex>A</tex> в <tex>B</tex> по символу <tex>c</tex>, и <tex> B </tex> является допускающим состоянием в автомате, добавим в грамматику правило <tex> A \to c </tex>.
Докажем, что если для автомата верно <tex>\langle S, \alpha \rangle \vdash^* \langle U, \varepsilon \rangle </tex>, то для построенной грамматики верно <tex> S \Rightarrow^* \alpha U </tex>. Будем доказывать индукцией по переходам в автомате.
