3.11.1. Расширенный магазинный автомат

Рассмотренный пример показывает, что автомат, выполняющий операцию свертки, в отличие от нисходящего распознавателя, не строит в магазине вывод цепочки, начиная с аксиомы грамматики, который соответствует построению синтаксического дерева цепочки "сверху - вниз", а выполняет  сворачивание символов, записанных в магазин. Такой порядок сворачивания символов, записанных в магазин, соответствует правому выводу цепочки, выполняемому "снизу - вверх". Это обстоятельство объясняет, почему такие распознаватели называются восходящими. Подобный распознаватель должен учитывать при переходе не один символ, расположенный в вершине магазина, а цепочку символов. Чтобы устранить отмеченное противоречие, определим новый тип автомата, который назовемрасширенным магазиннным автоматом.

Определение.                           Формальное определение такого автомата имеет вид:      M = {P, S, H, F, s0, h0, },  где       P - входной алфавит,      S - алфавит состояний,      s0- начальное состояние , s0 S,    F - множество конечных состояний, F является подмножеством S,     H - алфавит магазинных сисмволов, записываемых на вспомогательную ленту,     h0- маркер дна, он всегда записывается на дно магазина, h0H, : S {P  {$}}  H*  SH* - функция переходов.

 

В функциональном виде функции переходов расширенного автомата можно записать так:

     (s, p, ) = (s, ),

где   H*, p  (P  {$}) и s  S. Приведенное определение показывает, что расширенный автомат допускает замену одной цепочки, находящейся в вершине автомата, другой цепочкой. Используя введенное  ранее определение конфигурации  автомата, работу расширенного  магазинного автомата можно представить в виде последовательности сменяющих друг друга конфигураций. При этом начальная и конечная конфигурации имеют вид:

(s₀,  h₀) и (s₁, $, h₀I ),

где  заданная цепочка, s₁ - одно из заключительных состояний автомата, I - начальная аксиома грамматики. Цепочку и язык, допускаемые расширенным автоматом, можно определить так.

Определение. Цепочка допускается расширенным автоматом, если                      существует  последовательность конфигураций,                        первая из которых является начальной конфигурацией                         с заданной цепочкой, а последней  конфигурацией в                          последовательности является одна из                           заключительных конфигураций.( s0,  h0 )  , $|--  ( s1, h0I ),     где s1 - одно из заключительных состояний,  заданная  цепочка. Определение. Язык, допускаемый расширенным автоматом, можно                        определить  так: L(M) = { (s0,  h0 )  |--  ( s1, $,$ ) и  s1F}.

3.11.2. Пример работы расширенного магазинный автомат

В качестве иллюстрации работы расширенного автомата рассмотрим автомат, допускающий язык L={^R |a, b}*}.

M3.1:    P = {a, b}, S = {s₀, s₁},  H = {a, b, <I>, h₀}, F = {s₁} ,  

(s₀, a, h₀) = (s₀, h₀a),                 (s₀, a, <I>) = (s₀, <I>a), (s₀, b, h₀) = (s₀, h₀b),                (s₀, b, <I>) = (s₀, <I>b), (s₀, a, a) = (s₀, aa),                    *(s₀, a, a<I>a) = (s₀, <I>), (s₀, b, a )= (s₀, ba),                   *(s₀, b, a<I>a) = (s₀, <I>), (s₀, a, b) = (s₀, ab),                   *(s₀, a, b<I>b) = (s₀, <I>), (s₀, b, b) = (s₀, bb),                  *(s₀, b, b<I>b) = (s₀, <I>), *(s₀, a, aa) = (s₀, <I>),             *(s₀, $, a<I>a) = (s₀, <I>), *(s₀, b, aa) = (s₀, <I>),             *(s₀, $, b<I>b) = (s₀, <I>), *(s₀, a, bb) = (s₀, <I>),             *(s₀, $, h₀<I>) = (s₁, $). *(s₀, b, bb) = (s₀, <I>),

Это недетерминированный автомат. Если на входе задана цепочка abba, то его работу можно представить в виде следующего ряда конфигураций:  

№	Вход	Магазин	Состояние
1.	abba|-	h0	s0
2.	bba|-	h0a	s0
3.	ba|-	h0ab	s0
4.	a|-	h0abb	s0
5.	a|-	h0a<I>	s0
6.	|-	h0a<I>a	s0
7.	|-	h0<I>	s1