Изменения

'''Праволинейной грамматикой''' <tex>\Gamma</tex> (англ. ''right linear grammar'') называется [[Формальные_грамматики | грамматика]], в которой все правила имеют вид <tex> A \to a </tex>, <tex> A \to aB </tex>.

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

Пусть имеется конечный автомат. Построим для него праволинейную грамматику. Множеством нетерминалов нашей грамматики будет множество состояний автомата. Для каждой пары состояний автомата <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>. Будем доказывать индукцией по переходам в автомате.

::* Базой индукции будут переходы за <tex> 0 </tex> шагов.::* Индукционный переход: пусть данное свойство выполняется для переходов длины <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> S \Rightarrow^* \alpha U </tex> следует <tex> \langle S, \alpha \rangle \vdash^* \langle U, \varepsilon \rangle </tex>. Доказательство так же также проведем по индукции. Индукция будет идти по количеству примененных подряд правил.

::* Базой индукции будут строки, выводимые в грамматике из начального нетерминала <tex> S </tex> за <tex> 0 </tex> применений правил.

::* Индукционный переход: пусть верно для <tex>k-1</tex> применения правил. Рассмотрим произвольную строку, полученную за <tex>k</tex> применений правил. Рассмотрим последнее применение правила. Если оно имело вид <tex> A \to aB </tex>, значит в автомате возможен переход <tex> \langle A,a \rangle \vdash \langle B,\varepsilon \rangle </tex>, а если <tex> A \to a </tex>, то <tex> B </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>.

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

:* Докажем, что если слово допускается автоматом, то его можно вывести в грамматике. Рассмотрим слово <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>.}}==См. также==* [[Разрешимые_(рекурсивные)_языки|Разрешимые (рекурсивные) языки]]*[[Иерархия Хомского формальных грамматик]]* [[Возможность_порождения_формальной_грамматикой_произвольного_перечислимого_языка|Возможность порождения формальной грамматикой произвольного перечислимого языка]]

Теорема доказана== Источники информации ==* ''Michael A.Harrison'' Introduction to Formal Language Theory. — Addison-Wesley, 1978. — ISBN 978-0201029550. (с 19-20, 60-63.)* [[wikipedia:en:Linear grammar#Relationship with regular grammars|Wikipedia {{---}} Linear grammar]]