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

   презентация о кране 100 т, ул. |     

Работа магазинного автомата


Чтобы описать как работает автомат, введем понятие конфигурации.
 

Определение.    Конфигурацией автомата М называют тройку (s, a , g ) 

О  S x P* x H* ,

где s - текущее состояние управляющего устройства,
a -неиспользованная часть входной цепочки a

О P* ,самый левый символ этой цепочки a находится под головкой. Если a =e , то считается, что входная цепочка прочитана.
g -цепочка , записанная в магазине, g

О H* ,самый правый символ цепочки считается вершиной магазина. Если g=

$ , то магазин пуст.
Работа автомата может быть представлена как смена конфигураций. Один такт работы автомата заключается в определении новой конфигурации по заданной. Это записывается так:
 
                                                ( s, aa , g h ) |-- ( s', a , gb )

При этом предполагается, что автомат читает символ a, находящийся под головкой, и символ h,
находящийся в вершине магазина, определяет новое состояние s'

и записывает цепочку b



в
магазин вместо символа h. Если b =$ , то верхний символ оказывается удаленным из магазина.
Такая смена конфигураций возможна, если функция f( s, a, h ) определена и ей принадлежит
значение ( s', b ).

Описанный такт работы выполняется с перемещением головки. Для описания работы автомата нам потребуется другой вид такта, предполагающий изменение состояний и магазина без перемещения входной головки. Если  f0(s, e, h) определена и ей принадлежит значение (s', b )

, то он определяет смену конфигураций так:
 

      ( s, aa , g

      h ) |-- ( s', aa , gb )

    Таким образом, могут быть три случая при работе автомата:

       f(s, a, h) определена и выполняется такт работы,

       f(s, a, h) не определена, но определена функция f0(s, e, h) и выполняется пустой такт.


       Функции 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 ).


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

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

           


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