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