АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ Автоматы и преобразователи с магазинной памятью играют важную роль при построении автоматно-лингвистических моделей различного назначения, связанных с использованием бесконтекстных (контекстно-свободных) языков. В частности, такие устройства используются в большинстве работающих программ для синтаксического анализа программ, написанных на различных языках программирования, которые во многих случаях можно рассматривать как бесконтекстные. В отличие от конечных автоматов и преобразователей, автоматы с магазинной памятью снабжены дополнительной магазинной памятью (рабочей лентой). На рис. 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', ?').
    Вводится и такое обозначение: a1...an: (q, ?)+ * (q', ?'), если справедливо, что ai: (qi, ?i)+ (qi+1, ?i+1), 1 ? i ? m где ai Є V, ?1 = ?, ?2,..., ?n+1 = ?' Є V*m q1 = q, q2,..., qn+1 = q' Є Q Существует два способа определения языка, допускаемого магазинным автоматом. ............