Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 40 стр.

    Bc → F - из состояния В при поступлении на вход терминала c автомат переходит в
заключительное состояние F;
    Bc → A - из состояния В при поступлении на вход терминала c автомат переходит в
состояние А;
    Aa → A - в состоянии А при поступлении на вход терминала а автомат остается в этом
же состоянии А;
    Ab → S - из состояния A при поступлении на вход терминала b автомат переходит в
состояние S.
    Полученный недетерминированный конечный автомат распознает цепочки языка,
порождаемые праворекурсивной грамматикой G.
    Теорема. Для произвольного конечного автомата существует эквивалентная
праволинейная грамматика.
    Доказательство. Каждому состоянию произвольного автомата поставлен в соответствие
нетерминал грамматики, причем начальному состоянию будет соответствовать аксиома.
    Тогда для каждой команды Ac → B в множество правил грамматики включим правило A
→ cB, причем в случае, если B - заключительное состояние, добавим правило A → c.
Эквивалентность исходного конечного автомата и построенной грамматики очевидна.
    Теорема. Для каждой леворекурсивной грамматики существует эквивалентный
конечный автомат.
    Доказательство. Каждому нетерминальному символу произвольной леворекурсивной
грамматики поставим в соответствие состояние конечного автомата, причем состояние,
соответствующее аксиоме S, сделаем заключительным. Добавим еще одно состояние N и
сделаем его начальным состоянием.
    Каждому правилу грамматики A → Ba поставим в соответствие команду автомата Вa →
A. Тогда каждому выводу в грамматике:
       S⇒A1ak⇒A2ak-1ak⇒ ... ⇒Ak-1a2a3...ak ⇒ a1a2 . . . ak однозначно соответствует
следующая последовательность команд построенного автомата A:

   Na1 → Ak-1; . . .; A2ak-1 → A1; A1ak → S.

    Таким образом, язык L(G) = L(A).
    Теорема. Для произвольного конечного автомата существует эквивалентная
леворекурсивная грамматика.
    Доказательство. Каждому состоянию произвольного автомата поставим в соответствие
нетерминальный символ грамматики, добавим нетерминал S и сделаем его аксиомой.
    Каждой команде Aa → B в множество правил включим соответствующее правило B →
Aa, причем в том случае, если B - заключительное состояние, дополнительно введем правило
S → Aa, а если A - начальное состояние, то дополнительно введем правило B → a.
    Тогда последовательности команд:

    A0a1 → A1; A1a2 → A2; . . . ; Ak-1ak → F

      соответствует следующий вывод:

   S ⇒ Ak-1ak ⇒ ... ⇒ A1a2a3...ak ⇒ a1a2a3...ak.

    Важной особенностью автоматных грамматик является возможность представления их с
помощью конечных графов. По графу грамматики легко отыскивается вывод нужной
цепочки.