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

АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ Автоматы и преобразователи с магазинной памятью играют важную роль при построении автоматно-лингвистических моделей различного назначения, связанных с использованием бесконтекст­ных (контекстно-свободных) языков. В частности, такие устройства используются в большинстве работающих программ для синтаксического анализа программ, написанных на различных языках программирования, которые во

многих случаях можно рассматри­вать как бесконтекстные. В отличие от конечных автоматов и преобразователей, автоматы с магазинной памятью снабжены дополнительной магазинной памятью (рабочей лентой). На рис. 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 Как и в случае конечных автоматов, преобразователи с магазинной памятью