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

Формально детерминированный магазинный автомат определяется как следующая совокупность объектов: M = (V, Q, V M , , q 0 , z 0 , F), где V , Q , q 0 Є Q , F определяются так же, как и для конечного автомата; V M = { z 0 , z 1 ,…, z p -1 } — алфавит магазинных символов автомата; — функция, отображающая множество Q X ( V U { }) X V M в множество Q X V M , где е — пустая цепочка; z 0 Є V M — так называемый граничный маркер, т. е. символ, первым появляющийся в магазинной памяти.

Недетерминированный магазинный автомат отличается от детерминированного только тем, что функция отображает множество Q X ( V U { }) X V M . в множество конечных подмножеств Q x V M Как и в случае конечных автоматов, преобразователи с магазинной памятью отличаются от автоматов с магазинной памятью наличием выходной ленты. Далее будем рассматривать только недетерминированные магазинные автоматы.

Рассмотрим интерпретацию функции для такого автомата. Эту функцию можно представить совокупностью команд вида (q, a, z) (q 1 , 1 ),…,(q m , m ), где q, q 1 ,…q m Є Q, a Є V, z Є V M , 1 ,…, m Є V * m При этом считается, что если на входе читающей головки авто мата находится символ а, автомат находится в состоянии q , а верхний символ рабочей ленты z , то автомат может перейти к состоянию q i , записав при этом на рабочую ленту цепочку i (1 i m ) вместо символа z , передвинуть входную головку на один символ вправо так, как это показано на рис. 1, и перейти в состояние q i . Крайний левый символ i должен при этом оказаться в верхней ячейке магазина.

Команда ( q , e , z ) ( q 1 , 1 ),…, ( q m , m ) означает, что независимо от входного символа и, не передвигая входной го - + ловки, автомат перейдет в состояние q i , заменив символ z магазина на цепочку i (1 i m ). • Ситуацией магазинного автомата называется пара ( q , ) , где q Є Q , Є V * m . Между ситуациями магазинного автомата ( q , ) и ( q ’, ’) , устанавливается отношение, обозначаемое символом , если среди команд найдется такая, что (q, a, z) (q 1 , 1 ),…,(q m , m ), причем = z , ’ = i q ' = q i для некоторого 1 i m (z Є V m , Є V * m ). Говорят, что магазинный автомат переходит из состояния ( q , ) в состояние ( q ’, ’) и обозначают это следующим образом: a: (q, ) (q’, ’) . Вводится и такое обозначение: a 1 ...a n : (q, ) * (q’, ’), если справедливо, что a i : (q i , i ) (q i+1 , i+1 ), 1 i m где a i Є V , 1 = , 2 ,…, n +1 = ’ Є V * m q 1 = q , q 2 ,…, q n +1 = q ’ Є Q Существует два способа определения языка, допускаемого магазинным автоматом.

Согласно первому способу считается, что входная цепочка Є V * принадлежит языку L 1 ( M ) тогда, когда после просмотра последнего символа, входящего в эту цепочку, в магазине автомата М будет находиться пустая цепочка . Другими словами, L 1 (M) = { | : (q 0 , z 0 ) * (q, )} где q Є Q . Согласно второму способу считается, что входная цепочка принадлежит языку L 2 ( M ) тогда, когда после просмотра последнего символа, входящего в эту цепочку, автомат М окажется в одном из своих заключительных состояний q f Є F . Другими словами, L 2 ( M ) = { | : ( q 0 , z 0 ) * ( q f , )} где Є V * m , q f Є F Доказано, что множество языков, допускаемых произвольными магазинными автоматами согласно первому способу, совпадает с множеством языков, допускаемых согласно второму способу.

Доказано также, что если L ( G 2 ) — бесконтекстный язык, порождаемый Грамматикой G 2 = ( Vx , V T , Р, S ) , являющейся нормальной формой Грейбах, произвольной бесконтекстной грамматики G , то существует недетерминированный магазинный автомат М такой, что L 1 ( M ) = L ( G 2 ). При этом M = (V, Q, V m , , q 0 , z 0 , 0 ), Где V=V T ; Q={q 0 }; V M =V N ; z 0 =S а для каждого правила G 2 вида A a , a Є V T , a Є V * n строится команда отображения : (q 0 , a, A) (q 0 , a) Apia логично для любого недетерминированного магазинного автомата М, допускающего язык L 1 ( M ) , можно построить бесконтекстную грамматику G такую, что L ( G ) = L 1 ( M ). Если для конечных автоматов детерминированные и недетерминированные модели эквивалентны по отношению к классу допускаемых языков, то этого нельзя сказать для магазинных автоматов.