Формальные языки


Работа магазинного автомата - часть 2


  •  Функции f(s, a, h) и f0(s, e, h)  

    не определены, в этом случае дальнейшая работа автомата невозможна.

  • В общем виде действия, задаваемые функцией переходов и выполняемые автоматом,  демонстрирует следующая форма записи:
     

      f(s, <входной символ>, <магазинный символ>)=(s1, <заносимая цепочка>)

    При этом следует иметь в виду, что при выполнении такта вначале читается символ в вершине, а затем на его место заносится новый символ или цепочка.  Отдельные значения функции переходов часто называют командами магазинного автомата.
    Начальной конфигурацией называется конфигурация (sо, a

    , hо) , где

    -начальное состояние и

    - маркер дна магазина, а заключительной - конфигурация (s, $ , $) , где s принадлежит множеству конечных состояний F.


    Для обозначения последовательности сменяющих друг друга конфигураций условимся
    использовать знак |--*. Таким образом последовательность
     

          ( s1, a 1, g

          1 ) |-- ( s2, a 2, g 2) |-- ...|-- ( sn, a n,g

          n )

    записывается в сокращенном виде так:
     

                (s1,a

                1, g 1 ) |--* ( sn, a n,g

                n ).

  •  

    Пред.Страница 

    След.Страница   Раздел   Содержание


  •  




    - Начало -  - Назад -