АВТОМАТ МАГАЗИННЫЙ

— автомат специального вида (как правило, бесконечный), в основе которого лежит понятие памяти магазинной, или магазина. Магазин удобно представлять в виде бесконечной в одну сторону ленты, состоящей из ячеек, пронумерованных числами лента расположена вертикально таким образом, что первая ячейка оказывается самой верхней. В каждый момент времени в магазине записано некоторое слово. Первая его буква записана в первой ячейке, вторая — во второй и т. д. Остальные ячейки магазина «пусты», т. е. заполнены спец. «пустыми» символами. Магазин работает в двух режимах — чтения и записи. При чтении воспринимается лишь верхняя буква слова, записанного в магазине. Эта буква стирается, а оставшаяся часть слова поднимается на одну ячейку вверх. При записи в магазин слова h длины слово, записанное там, сдвигается на ячеек вниз, а в освободившиеся ячейки записываются символы слова h. Таким образом, чтение слова из магазина происходит в обратном порядке по сравнению с порядком его записи.

Структура А. м. представлена на рис. Он состоит из конечного управляющего автомата, снабженного тремя каналами для работы с магазинами — входным, выходным и внутренним. При этом входной магазин работает всегда только в режиме чтения, выходной — в режиме записи, а внутренний — в режиме чтения и записи. Множество А состояний управляющего автомата разбито на два непересекающихся подмножества

Структура магазинного автомата,

Если состояние управляющего автомата относится к подмножеству то Происходит считывание из входного и внутр. магазинов, если же оно относится к подмножеству то происходит считывание только из внутреннего магазина. В этот же момент автомат переходит в новое состояние и записывает во внутренний и выходной магазины некоторые слова. Пусть X, Y и Z — алфавиты входного, выходного и внутреннего магазинов, не включающие «пустой» буквы. Тогда А. м. задается двумя ф-циями

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

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

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

Для распознающих автоматов в определении конфигурации следует отбросить четвертую компоненту, а для порождающих — первую. В мн-ве А выделяют также начальное состояние и мн-во заключительных состояний А, а в мн-ве Z — начальный символ Распознающий А. м. представляет (распознает) язык, состоящий из всех слов таких, что конфигурация переходит в одну из заключительных конфигураций. Порождающий автомат порождает язык, состоящий из всех слов q таких, что конфигурация переходит в заключительную конфигурацию вида . Класс языков, распознаваемых (порождаемых) недетерминированными А. совпадает с классом контекстно-свободных языков, а класс отношений, представленных недетерминированными магазинными преобразователями, совпадает с классом отношений, порождаемых контекстно-свободными грамматиками перевода.

Лит.: Гинзбург С. Математическая теория контекстно-свободных языков. Пер. с англ. М., 1970 [библиогр. с. 310-319]- А. А. Летичевский.