Автоматы с магазинной памятью
Автоматы с магазинной памятью
Автоматы с магазинной памятью — вычислительная модель теории формальных языков, использующая стек для хранения информации.
Общие сведения
Автоматы с магазинной памятью используют стек для хранения информации.
Благодаря возможности сохранять данные о предыдущих состояниях такие автоматы способны распознавать контекстно‑свободные языки.
Эта модель значительно мощнее обычных конечных автоматов.
Автоматы с магазинной памятью широко используются при разработке компиляторов и синтаксических анализаторов.
Теоретические особенности
Формально автомат определяется через конфигурации и правила переходов.
Рассматриваются также автоматы с однобуквенными переходами и различные формы эквивалентности.