Автоматы с магазинной памятью

В теории автоматов, автомат с магазинной памятью — это конечный автомат, который использует стек для хранения состояний.

Формальное определение

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

Пример с использованием автомата с магазинной памятью