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

    3) команды сравнения и поглощения символа с входной ленты и символа в верхушке
магазина:
                              p1, a, a → p1, ε
                              p1, +, + → p1, ε
                              p1, /, / → p1, ε
                              p1, (, ( → p1, ε
                              p1, ), ) → p1, ε;

    4) команда завершения разбора:
                                      p1, ε, B0 → f, B0.
    Процесс разбора цепочки представлен в таблице 2.

      5.5. Выводы
    Рассмотренные выше МП-автоматы работают недетерминированно, то есть если цепочка
принадлежит языку, порождаемому заданной грамматикой, то какой-то из вариантов
функционирования автомата осуществит правильный разбор. Если же цепочка не
принадлежит языку, то никакой из вариантов разбора не приведет к цели.
    Отсутствие детерминированного эквивалентного автомата для произвольной КС-
грамматики означает невозможность построения универсальной простой однопроходной
программы синтаксического анализа. Поэтому для эффективного разбора необходимо
выделять специальные классы КС-грамматик, удовлетворяющие требованиям конкретных
типов анализаторов.
    Если требуется выполнить разбор для произвольной КС-грамматики, то придется
использовать детерминированную программную модель недетерминированного МП-
автомата.

      5.6. Понятие преобразователей
    Автоматы с выходом называются преобразователями. В зависимости от вида функции,
отображающей множество состояний и входных символов в множество выходных символов
и новых состояний, а также от типа рабочей ленты различают разные виды
преобразователей. Рассмотрим конечные автоматы-преобразователи.
    Конечным преобразователем называется шестерка вида

     P = (К, X, Y, f, g, q0), где
     K - конечное множество состояний;
     X - входной алфавит;
     Y - выходной алфавит;
     f - функция переходов;
     g - функция выходов;
     q0 - начальное состояние.
     Типы отображений f и g определяют различные виды автоматов. Если g - отображение
K ⋅ X в Y, то конечный преобразователь называется синхронным. В общем случае это
отображение имеет вид K ⋅ X → Y*.
     Пусть P = (К, X, Y, f, g, q0) - конечный преобразователь. Тогда отображение S(x) = g(q0,
x), определенное для любой цепочки x ∈ X*, называется конечным преобразователем.
     Заметим, что для того чтобы выходную цепочку y можно было считать переводом
входной цепочки x, цепочка x должна перевести преобразователь из начального состояния в
заключительное.