Правоконтекстные грамматики, эквивалентность автоматам

Определение:

Праволинейной грамматикой [math]\Gamma[/math] называется грамматика, в которой все правила имеют вид [math] A \to a [/math], [math] A \to aB [/math].

Аналогично можно определить леволинейные грамматики.

Теорема:

Множество языков, задаваемых праволинейными грамматиками совпадает со множеством языков, задаваемых конечными автоматами.

Доказательство:

[math]\triangleright[/math]

Пусть имеется конечный автомат. Построим для него праволинейную грамматику. Множеством нетерминалов нашей грамматики будет множество состояний автомата. Для каждой пары состояний автомата [math]A[/math] и [math]B[/math] таких, что имеется переход из [math]A[/math] в [math]B[/math] по символу [math]c[/math], и [math] B [/math] – не является допускающим состоянием в автомате, добавим в грамматику правило [math] A \to cB [/math]. Затем для каждой пары состояний автомата [math]A[/math] и [math]B[/math] таких, что имеется переход из [math]A[/math] в [math]B[/math] по символу [math]c[/math], и [math] B [/math] – является допускающим состоянием в автомате, добавим в грамматику правило [math] A \to c [/math]. Докажем, что если для автомата верно [math]\langle S, \alpha \rangle \vdash^* \langle U, \varepsilon \rangle [/math], то для построенной грамматики верно [math] S \Rightarrow^* \alpha U [/math]. Будем доказывать индукцией по переходам в автомате. Базой индукции будут переходы за 0 шагов. Индукционный переход: пусть данное свойство выполняется для переходов длины [math]k-1[/math]. Докажем что верно и для переходов за [math]k[/math] шагов. Рассмотрим переход [math]\langle S, \alpha \rangle \vdash^{k} \langle U, \varepsilon \rangle [/math], а именно его последний шаг: [math] \langle S, \alpha \rangle \vdash^{k-1} \langle Q, c \rangle \vdash \langle U, \varepsilon \rangle [/math] Так как для [math]k-1[/math] шагов верно, то [math] S \Rightarrow^{k-1} \alpha c^{-1} Q [/math] но по построению грамматики имеется правило [math] Q \to c U[/math], значит [math] S \Rightarrow^{k-1} \alpha c^{-1} Q \Rightarrow \alpha c^{-1} c U = \alpha U[/math]. Таким образом доказали для [math]k[/math] шагов. Теперь пусть имеется праволинейная грамматика. Построим по ней конечный детерминированный автомат. Введем специальное допускающее состояние [math] ok [/math]. Множеством состояний автомата будет множество нетерминалов грамматики вместе с состоянием [math] ok [/math] ([math] Q = N \cup ok [/math]). Для правил вида [math] A \to aB [/math] определим функцию перехода в автомате как [math] \delta \left( A, a \right) = B [/math]. Для правил вида [math] A \to a [/math] определим функцию перехода в автомате как [math] \delta \left( A, a \right) = ok [/math]

[math]\triangleleft[/math]