Теория формальных языков, грамматик и автоматов. Ишакова Е.Н. - 28 стр.

      Общая схема МП-автомата представлена на рисунке 5.1.

          a1 a2                      an Входная цепочка символов

               Считывающая
               головка
                                     Стек
                               N1    (магазин)
          УУ                   N2
                               N3
       Управляющее             …
       устройство


                             Рисунок 5.1 – Схема МП-автомата
                  Алгоритм 5.1. Функционирование МП-автомата
        Начальной конфигурацией МП-автомата является конфигурация
(q0, ω , N0).
        Шаг работы МП-автомата будем представлять в виде отношения непо-
средственного следования конфигураций (обозначается «|=») и отношения дос-
тижимости конфигураций (обозначается «|=*»). Если одним из значений мага-
зинной функции F (q ∈ Q, t ∈ (T ∪ {ε }), S ∈ N ) является (q′ ∈ Q, γ ∈ N * ) , то запи-
сывается (q, tω , Sα ) |= (q′, ω , γα ) . При этом возможны следующие варианты.
        1) Случай t ∈ T. Автомат находится в текущем состоянии q, читает вход-
ной символ t, имеет в вершине стека символ S. Он переходит в очередное со-
стояние q′ , сдвигает входную головку на ячейку вправо и заменяет верхний
символ S строкой γ магазинных символов. Вариант γ = ε означает, что S удаля-
ется из стека.
        2) Случай t = ε . Отличается от первого случая тем, что входной символ t
просто не принимается во внимание, и входная головка не сдвигается. Такой
шаг работы МП-автомата называется ε -шагом, который может выполняться
даже после завершения чтения входной строки.
        Заключительной конфигурацией МП-автомата является конфигурация
(q, ε , α ), где q ∈ Z.
        Определение 5.3. МП-автомат допускает входную стоку ω , если сущест-
вует путь по конфигурациям (q0 , ω , N 0 ) |= *(q, ε , α ) для некоторых q ∈ Z и
α ∈ N*.
     Определение 5.4. Язык L, распознаваемый (принимаемый) МП-
автоматом М определяется как множество вида:

      L( M ) = {ω | ω ∈ T * и (q0 , ω , N 0 ) |= * (q, ε , α ) для некоторых q ∈ Z и
α ∈ N * }.

28