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

Рис. 1.  
Головка входной ленты может перемещаться только в одну сторону - вправо или оставаться на месте. Она может выполнять только чтение. Головка вспомогательной ленты способна выполнять как чтение, так и запись, но эти операции связаны с перемещением головки определенным образом:
- при записи головка предварительно сдвигается на одну позицию вверх, а затем символ заносится на ленту,
- при чтении символ, находящийся под головкой считывается с ленты, а затем головка сдвигается на одну позицию вниз, т.о.головка всегда установлена против последнего записанного символа. Позицию, находящуюся в рассматриваемый момент времени под головкой, называют вершиной магазина.

Определение. Магазинный автомат М определяется следующей совокупностью семи объектов:

M = {P , S , sо , f , F , H , hо }, где

P - входной алфавит,
S - алфавит состояний,
sо - начальное состояние,
sо S ,
F - множество конечных состояний, F является подмножеством S,
H - алфавит магазинных символов, записываемых на вспомогательную ленту,
hо - маркер дна, он всегда записывается на дно магазина, hо H,
f - функция переходов
f : {P { ε }} x S x H S x H*,
если М - автомат детерминированный, и
f:{P { ε }} x S x H M( S x H*) ,
если М - автомат недетерминированный.

Функция f отображает тройки ( pi, sj, hk) в пары ( sr, υ ), где υ H* и hk - символ в вершине магазина, для детерминированного автомата или в множество пар для недетерминированного автомата.
Эта функция описывает изменение состояния магазинного автомата, происходящее при чтении символа с входной ленты и премещении входной головки.
В дальнейшем при построении магазинных автоматов потребуются две разновидности функций переходов, изменяющих состояние автомата без перемещения входной головки:
1) функция переходов с пустым символом в качестве входного символа:

f0(s, ε, h) = (s', β),

которая, независимо от того какой символ находится под читаюшей гловкой входной ленты, предписывает прочитать символ h из вершины магазина, изменить состояние автомата на s' и записать цепочку β в магазин.

2) функция переходов с определенным входным символом:

f*(s, a, h) = (s', β),

которая предписывает изменение состояния и запись цепочки в магазин при условии, что символ a читается входной головкой, а в вершине магазина находится символ h.