Изменения

'''Праволинейной грамматикой''' <tex>\Gamma</tex> называется грамматика, в которой все правила имеют вид<tex> A \to a </tex>, <tex> A \to aB </tex>.}} Аналогично можно определить леволинейные грамматики. {{Теорема|statement=Множество языков, задаваемых праволинейными грамматиками совпадает со множеством языков, задаваемых конечными автоматами.|proof=Пусть имеется конечный автомат. Построим для него праволинейную грамматику. Множеством нетерминалов нашей грамматики будет множество состояний автомата. Для каждой пары состояний автомата <tex>A</tex> и <tex>B</tex> таких, что имеется переход из <tex>A</tex> в <tex>B</tex> по символу <tex>c</tex>, и <tex> B </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>. Будем доказывать индукцией по переходам в автомате. Базой индукции будут переходы за 0 шагов.Индукционный переход: пусть данное свойство выполняется для переходов длины <tex>k-1</tex>. Докажем что верно и для переходов за <tex>k</tex> шагов. Рассмотрим переход <tex>\langle S, \alpha \rangle \vdash^{k} \langle U, \varepsilon \rangle </tex>, а именно его последний шаг: <tex> \langle S, \alpha \rangle \vdash^{k-1} \langle Q, c \rangle \vdash \langle U, \varepsilon \rangle </tex>Так как для <tex>k-1</tex> шагов верно, то <tex> S \Rightarrow^{k-1} \alpha c^{-1} Q </tex> но по построению грамматики имеется правило <tex> Q \to c U</tex>, значит <tex> S \Rightarrow^{k-1} \alpha c^{-1} Q \Rightarrow \alpha c^{-1} c U = \alpha U</tex>. Таким образом доказали для <tex>k</tex> шагов. Теперь пусть имеется праволинейная грамматика. Построим по ней конечный детерминированный автомат. Введем специальное допускающее состояние <tex> ok </tex>. Множеством состояний автомата будет множество нетерминалов грамматики вместе с состоянием <tex> ok </tex> (<tex> Q = N \cup ok </tex>). Для правил вида <tex> A \to aB </tex> определим функцию перехода в автомате как <tex> \delta \left( A, a \right) = B </tex>. Для правил вида <tex> A \to a </tex> определим функцию перехода в автомате как <tex> \delta \left( A, a \right) = ok </tex>