Магазинный автомат

В общем виде МП-автомат можно определить следующим образом:

R(Q, V, Z, d, q₀, z₀, F),

где Q — множество состояний автомата;

V — алфавит входных символов автомата;

Z — специальный конечный алфавит магазинных символов автомата (обычно он включает в себя алфавиты терминальных и нетерминальных символов грамматики),

V Í Z;

d — функция переходов автомата, которая отображает множество Qx(V È {l})xZ на конечное множество подмножеств P(QxZ');

q ₀ Î Q — начальное состояние автомата;

z₀ Î Z — начальный символ магазина;

F Í Q — множество конечных состояний.

МП-автомат в отличие от обычного конечного автомата (КА) имеет стек (магазин), в который можно помещать специальные «магазинные» символы (обычно это терминальные и нетерминальные символы грамматики языка). Переход из одного состояния в другое зависит не только от входного символа, но и от одного или нескольких верхних символов стека. Таким образом, конфигурация автомата определяется тремя параметрами: состоянием автомата, текущим символом входной цепочки (положением указателя в цепочке) и содержимым стека.

Рисунок 2 -3. Общая условная схема автомата с магазинной памятью (МП-автомата)

При выполнении такта (перехода) из стека удаляется верхний символ, соответствующий условию перехода, и добавляется цепочка, соответствующая правилу перехода. Первый символ цепочки становится верхушкой стека. Допускаются переходы, при которых входной символ игнорируется (и тем самым он будет входным символом и следующем переходе). Эти переходы (такты) называются l-переходами (l-тактами). Аналогично, автомат не обязательно должен извлекать символ из стека — гда z=l., этого не происходит.

МП-автомат допускает (принимает) цепочку символов, если, получив эту цепочку на вход, он может перейти в одну из конечных конфигураций, — когда при окончании цепочки автомат находится в одном из конечных состояний, а стек содержит некоторую определенную цепочку. Тогда входная цепочка принимается (после окончания цепочки автомат может сделать произвольное количество l - переходов). Иначе цепочка символов не принимается.