АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ

Автоматы и преобразователи с магазинной памятью играют важную роль при построении автоматно-лингвистических моделей различного назначения, связанных с использованием бесконтекстных (контекстно-свободных) языков. В частности, такие устройства используются в большинстве работающих программ для синтаксического анализа программ, написанных на различных языках программирования, которые во многих случаях можно рассматривать как бесконтекстные.
В отличие от конечных автоматов и преобразователей,

автоматы с магазинной памятью снабжены дополнительной магазинной памятью
(рабочей лентой).
На рис. 1
| |

такой преобразователь. Конечное управляющее устройство снабжается дополнительной управляющей головкой, всегда указывающей на верхнюю ячейку магазинной памяти; за один такт работы автомата
(преобразователя) управляющая головка может произвести следующие движения:
1) стереть символ из верхней ячейки (при этом все символы, находящиеся на рабочей ленте, перемещаются на одну ячейку вверх);

2) стереть символ из верхней ячейки и записать на рабочую ленту непустую цепочку символов (при этом содержимое рабочей ленты сдвигается вниз ровно настолько, какова длина с записываемой цепочки).
Таким образом, устройство магазинной памяти можно сравнить с устройством магазина боевого автомата: когда в него вкладывается патрон, те, которые уже были внутри, проталкиваются вниз; достать можно только патрон, вложенный последним.
Формально детерминированный магазинный автомат определяется как следующая совокупность объектов:

M = (V, Q, VM, ?, q0, z0, F),

где V, Q, q0 Є Q, F определяются так же, как и для конечного автомата;
VM = {z0, z1,…,zp-1} — алфавит магазинных символов автомата;
? — функция, отображающая множество Q X (V U { ? }) X VM

в множество Q X VM, где е — пустая цепочка;

z0 Є VM — так называемый граничный маркер, т. е. символ,

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

Как и в случае конечных автоматов, преобразователи с магазинной памятью отличаются от автоматов с магазинной памятью наличием выходной ленты.
Далее будем рассматривать только недетерминированные магазинные автоматы.
Рассмотрим интерпретацию функции ? для такого автомата. Эту функцию можно представить совокупностью команд вида

(q, a, z)>(q1, ?1),…,(qm, ?m),

где q, q1,…qm Є Q, a Є V, z Є VM, ?1,…,?m Є V*m

При этом считается, что если на входе читающей головки авто

мата находится символ а, автомат находится в состоянии q, а верхний символ рабочей ленты z, то автомат может перейти к состоянию qi, записав при этом на рабочую ленту цепочку ?i(1 ? i ? m)

вместо символа z, передвинуть входную головку на один символ

вправо так, как это показано на рис. 1, и перейти в состояние qi. Крайний левый символ ?i должен при этом оказаться в верхней

ячейке магазина. Команда (q, e, z)>(q1, ?1),…, (qm, ?m) означает,

что независимо от входного символа и, не передвигая входной го- +

ловки, автомат перейдет в состояние qi, заменив символ z магазина

на цепочку ?i(1 ? i ? m). •
Ситуацией магазинного автомата называется пара (q, ?), где q Є Q, ? Є V*m. Между ситуациями магазинного автомата (q, ?) и
(q’, ?’), устанавливается отношение, обозначаемое символом +, если среди команд найдется такая, что

(q, a, z)>(q1, ?1),…,(qm, ?m),

причем ? = z?, ?’ = ?i? q' = qi для некоторого 1 ? i ? m (z Є Vm,

? Є V*m ).
Говорят, что магазинный автомат переходит из состояния (q, ?) в состояние
(q’, ?’) и обозначают это следующим образом:

a: (q, ?)+ (q’, ?’).