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

    Любой вывод цепочки в автоматной грамматике соответствует пути в графе этой
грамматики, который начинается из вершины S (вершины, помеченной аксиомой) и
заканчивается в конечной вершине.
    Пример. Построить конечный автомат, распознающий язык L(A) = {(ab)*}.
    Сначала построим некоторую грамматику G, которая бы порождала язык L(A):
    S → aA;
    A → bS | b.
    Проверим, действительно ли эта грамматика порождает язык L(A). Для этого построим
несколько выводов возможных вариантов цепочек:

    1) S ⇒ aA ⇒ ab;
    2) S ⇒ aA ⇒ abS ⇒ abaA ⇒ abab;
    3) S ⇒ aA ⇒ abS ⇒ abaA ⇒ ababS ⇒ ababaA ⇒ ababab; и т.д.
    Таким образом, грамматика G действительно порождает язык L(A), следовательно,
можно построить соответствующий этой грамматике конечный автомат. Для этого введем
заключительное состояние F, начальное состояние соответствует аксиоме S.
                    b
           S                 А

                    a


                             b

                             F




    Запишем преобразование правил вывода в команды:
    Sa → A - из состояния S при поступлении на вход терминала а автомат переходит в
состояние А;
    Ab → S - из состояния А при поступлении на вход терминала a автомат переходит в
состояние S;
    Ab → F - из состояния А при поступлении на вход терминала b автомат переходит в
заключительное состояние F.
    Таким образом, построен недетерминированный конечный автомат, распознающий
заданный язык L(G).

      5.4. Автоматы с магазинной памятью
    Автомат с магазинной памятью (МП-автомат) имеет рабочую ленту, которая
организована в виде магазина.
    МП-автомат - это семерка вида:
    M = (К, Σ, Г, δ, p0, F, B0), где
    К - конечное множество состояний;
    Σ - алфавит;
    Г - алфавит магазина;
    δ - функция переходов;
    p0 - начальное состояние;
    F - множество заключительных состояний;
    B0 - символ из множества Г для обозначения маркера дна магазина.
    В общем случае данное определение соответствует недетерминированному автомату.
    В отличие от конечного автомата для произвольного МП-автомата нельзя построить
эквивалентный детерминированный автомат.