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