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

Мы уже говорили о том, что теория конечных автоматов пригодна только для регулярных грамматик. Для контекстно-свободной грамматики вида

G = { {a, +, *, /, -,.,), (}, {E, T, F,}P, E }

P = { E®T, E®E + T, E®E – T,

T®F, T®T*F, T®T/ F,

F®a, F® (E) }

создать конечный распознающий автомат уже невозможно.

Для этого существуют более сложные по своей структуре автоматы – автоматы с магазинной памятью, которые применяются для распознавания фраз контекстно-свободных грамматик.

 

Определение. Автомат с магазинной памятью (МП-автомат или стековый автомат) - это семерка

МП = (å, Q, Г, q₀, z₀, T, P), где

å - конечный входной алфавит (входной словарь);

Q - конечное множество состояний;

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

q₀ - начальное состояние управляющего устройства (q₀ÎQ);

z₀ - символ, находящийся в магазине в начальный момент времени (начальный символ), z ₀ÎГ;

T - множество терминальных (заключительных) состояний, TÌQ;

P - отображение множества Q´(åÈ{e})´Г в множество конечных подмножеств множества Q´Г^*.

P: Q´(åÈ{e})´Г ® Q´Г^*

Условно МП-автомат можно изобразить так:

Конфигурацией МП-автомата называется тройка (q,w,a)ÎQ´å^*´Г^*, где

q - текущее состояние устройства;

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

a - содержимое магазина; самый левый символ цепочки a считается верхним символом магазина; если a=e, то магазин считается пустым.

 

Такт работы МП-автомата

(q,aw,Za)® (q', w,ga)

Если a=e, то этот такт называется e-тактом. В e-такте входной символ не принимается во внимание и входная головка не сдвигается. Если g=e, то верхний символ удаляется из магазина (магазинный список сокращается).

 

Начальная конфигурация МП-автомата – это тройка

(q₀, w, Z₀), wÎå^*

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

(q₀, w, Z₀) ®^*(q, e, a) для некоторых qÎT и aÎГ^*

На практике более полезным и универсальным является т.н. расширенный МП-автомат

МП_r = (å, Q, Г, q₀, Z₀, T, P_r), где

P_r - отображение множества Q´(åÈ{e})´Г^* в множество конечных подмножеств множества Q´Г^*, а все остальные символы имеют тот же смысл, что и в определении МП-автомата.

В отличие от МП-автомата расширенный МП-автомат обладает способностью продолжать работу и тогда, когда магазин пуст.

 

Теорема. Пусть G = (N,å,P,S) - КС-грамматика. По грамматике G можно построить такой МП-автомат R, что L_e(R)=L(G).

 

В качестве примера рассмотрим расширенный МП-автомат R, распознающий грамматику G₀

G₀=({E,T,F},{a,+,*,(,),#},P,E)

P = { E ® E+T|T

T ® T*F|F

F ® (E)|a}

Здесь # - символ конца входной последовательности.

Определим автомат следующим образом:

R = (å,Q,Г,q₀,Z₀,T,P), где

Q = {q,r},

Г={E, T, F, $} È å

q₀ = q,

Z₀ = $,

T = {r},

P:

(1) (q,e,E+T) ® (q,E) (*)

(2) (q,e,T) ® (q,E) (*)

(3) (q,e,T*F) ® (q,T)

(4) (q,e,F) ® (q,T)

(5) (q,e,(E)) ® (q,F)

(6) (q,e,a) ® (q,F)

(7) (q,#,$E) ® (r,e)

(8) (q,b,e) ® (q,b) для всех bÎ{a,+,*,(,)};

 

Замечание 1. Правила, отмеченные (*), применимы, если следующим символом входной цепочки является '+', или '-', ')' или входная цепочка пуста.

Замечание 2. Приоритет выполнения правил определяется содержимым стека.

 

Пусть на входе распознавателя цепочка "a+a*a". Тогда процесс ее распознавания будет выглядеть так:

(q,a+a*a#,$) ® (q, +a*a#, $a)

® (q, +a*a#, $F)

® (q, +a*a#, $T)

® (q, +a*a#, $E)

® (q, a*a#, $E+)

® (q, *a#, $E+a)

® (q, *a#, $E+F)

® (q, *a#, $E+T)

® (q, a#, $E+T*)

® (q, e, $E+T*a)

® (q, e, $E+T*F)

® (q, e, $E+T)

® (q, #, $E)

® (r, #, e)

 

Следует четко осознавать, что схема СУ-перевода и разбор КС-грамматики с помощью МП-автомата являются эквивалентными. В частности, если мы дополним МП-автомат набором семантических процедур, то МП-автомат, помимо синтаксического разбора, будет уметь формировать и польскую форму записи анализируемой фразы.

Более того, МП-автомат можно считать просто более формальным изложением алгоритма СУ-перевода. Например, алгоритм в СУ-перевода гласит: если ни одно из правил не применимо к содержимому стека, то следует поместить в стек очередной символ входной последовательности. В МП-автомате вместо этого используется правило (8). А условие завершения СУ-перевода формулируется правилом (7). Более того, если говорить о конкретной программной реализации обоих методов, то и в том, и в другом случае нам придется пользоваться практически эквивалентными структурами.