Автома́т з магази́нною па́м'яттю () — в теорії автоматів — скінченний автомат, що додатково використовує стек для зберігання станів.
На відміну від скінченних автоматів, автомат з магазинною пам'яттю формально визначається як набір , де
— скінченна множина станів автомата — єдиний допустимий початковий стан автомата — множина дозволених кінцевих станів, причому допускається F=Ø, і F=K — скінченна множина символів вхідного алфавіту, з якого формуються рядки, що зчитуються автоматом — алфавіт пам'яті (магазину чи стеку) — нульовий символ пам'яті. — функція переходів:
Пам'ять працює як стек, тобто для зчитування доступний лише останній записаний в ній елемент. Функція переходу за комбінацією поточного стану, вхідного символу і символу на вершині магазину визначає наступний стан (і, можливо, символ для запису в магазин). У випадку, коли в правій частині автоматного правила присутній , у магазин нічого не додається, а елемент з вершини стирається. Якщо магазин порожній, то спрацьовують правила з в лівій частині.
Автомат з магазинною пам'яттю може розпізнати будь-яку контекстно-вільну мову.
У чистому вигляді автомати з магазинною пам'яттю використовуються вкрай рідко. Зазвичай ця модель використовується для наочного подання відмінності звичайних скінченних автоматів від синтаксичних граматик. Реалізація автоматів з магазинною пам'яттю відрізняється від кінцевих автоматів тим, що поточний стан автомата сильно залежить від будь-якого попереднього.
Види автоматів з магазинної пам'яттю
Існують детерміновані та недетерміновані автомати з магазинною пам'яттю. Для недетермінованих автоматів (на відміну від детермінованих) існує два еквівалентні критерії завершення роботи: порожній магазин досягнення кінцевого стану Детермінований автомат завершує роботу лише тоді, коли досягає кінцевого стану.
Примітки
Джерела