автомат с магазинной памятью — это конечный автомат, который использует стек для хранения состояний.
В отличие от обычных конечных автоматов, автомат с магазинной памятью является набором[1]:
где
· K — конечное множество состояний автомата
· — единственно допустимое начальное состояние автомата
· — множество конечных состояний, причём допустимо F=Ø, и F=K
· Σ — допустимый входной алфавит, из которого формируются строки, считываемые автоматом
· S — алфавит памяти (магазина)
· — нулевой символ памяти.
Память работает как стек, то есть для чтения доступен последний записанный в неё элемент. Таким образом, функция перехода является отображением . То есть, по комбинации текущего состояния, входного символа и символа на вершине магазина автомат выбирает следующее состояние и, возможно, символ для записи в магазин. В случае, когда в правой части автоматного правила присутствует , в магазин ничего не добавляется, а элемент с вершины стирается. Если магазин пуст, то срабатывают правила с в левой части.
|
|
Автомат с магазинной памятью это формальная система, описываемая 5 формальными объектами:
1.Конечное множество входных символов с маркером входной цепочки
2. Конечное множество магазинных символов+маркер дна
3. Конечное множество состояний+начальное
4. УУ, которое каждой комбинации (вход. симв, магазинный симв., состояние) ставит в соответствие выход или переход. Переход – выполнение операции над магазином, состоянием и входом. Исключаются операции, которые вталкивают или выталкивают из магазина маркер дна и запрашивают начальный символ после маркера окончания.
5. Начальным содержимым магазина является маркер дна, за которым следует цепочка других магазинных символов.