Автоматы с магазинной памятью (мп  автоматы )

МП  автоматы представляют собой естественную модель синтаксических анализаторов КС  языков .

Определение. МП-автомат  это семерка

P =(Q ,  ,  ,  , q₀ , Z₀ , F ),

где Q  конечное множество символов состояний , представляющих всевозможные состояния управляющего устройства (УУ);

  конечный входной алфавит ;

  конечный алфавит магазинных символов ;

  отображение Q  (  {e})    (Q   ^ );

q₀  Q  начальное состояние УУ;

Z₀    символ , находящийся в магазине в начальный момен времени (начальный символ) ;

F  Q  множество заключительных состояний .

Структура МП - автомата показана на рис.2.4.

Рис.

Определение. Конфигурацией МП  автомата Р называется

тройка (q ,  , )  Q   ^*   ^* ,

где q  текущее состояние УУ;

w неиспользованная часть входной цепочки, причем первый символ цепочки  находится под входной головкой (если  =е , то считается, что вся входная лента прочитана);

  содержимое магазина , причем самый левый символ

цепочки  считается верхним символом магазина ( если  е , то магазин считается пустым ). 

Определение. Такт работы МП автомата Р будем представлять в виде бинарного отношения _р ,определенного на конфигурациях. Будем записывать (q, a , ) ( ,  , ), если множество

(q , a , ) содержит ( , ) , где q,  Q , a    {e} ,    ^* ,

   , ,   ^* . 

Если ае , то данная запись означает следующее :

МП  автомат Р , находясь в состоянии q и имея а в качестве текущего входного символа , расположенного над входной головкой , а   в качестве верхнего символа магазина , может перейти в новое состояние , сдвинуть входную головку на одну ячейку вправо и заменить верхний символ магазина цепочкой  магазинных символов. Если  = е , то верхний символ просто удаляется из магазина .

Если а=е, такт называется е- тактом . В таком такте текущий входной символ не принимается во внимание и входная головка не сдвигается . Однако состояния УУ и содержимое памяти могут изменяться .

Следующий такт невозможен , если магазин пуст .

Определение. Начальной конфигурацией МП  автомата Р называется конфигурация вида (q₀ ,  , ₀) , где    ^* , т.е. УУ находится в начальном состоянии , входная лента содержит цепочку, которую нужно распознать , а в магазине есть только начальный символ ₀ .

Заключительная конфигурация: (q , e , ) , где q  F ,   ^* .

Говорят , что цепочка  допускается МП  автоматом Р , если

(q₀ ,  , ₀) ^* (q , e , ) , для некоторых qF и    ^* .

Язык, определяемый (допускаемый ) автоматом P (обозначается L(P)),  это множество цепочек допускаемых Р . 

Пример . Пусть Р=( {q₀ , q₁ , q₂ },{0,1},{ ,0} ,  , q₀ , , {q₀ }),

где (q₀ , 0 , Z)={(q₁ , 0Z)};

(q₁ , 0 , 0)={(q₁ , 00)};

(q₁ , 1 , 0)={(q₂ , e)};

(q₂ , 1 , 0)={(q₂ , e)};

(q₂ , e , Z)={(q₀ , e)}.

Словесное описание функции  : МП  автомат копирует в магазин начальную часть входной цепочки , состоящую из нулей , а затем устраняет из магазина по одному нулю на каждую единицу, которую он видит на входе .

Рассмотрим, как этот автомат распознает  = 0011 :

(q₀ , 0011 , Z) ( q₁ , 011 , 0Z) (q₁ , 11 , 00Z)

(q₂ , 1 , 0Z) (q₂ , e , Z) (q₀ , e , e) < s t o p> .

17