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



Работа магазинного автомата - часть 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 ).

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

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


       




      Содержание  Назад