Автомат з магазинною пам'яттю

Автома́т з магази́нною па́м'яттю (англ. pushdown automaton) — в теорії автоматів — скінченний автомат, що додатково використовує стек для зберігання станів.

Класи автоматів

На відміну від скінченних автоматів, автомат з магазинною пам'яттю формально визначається як набір
${\displaystyle {\boldsymbol {M=(K,\Sigma ,\pi ,s,F,S,m)}}}$, де

• ${\displaystyle K}$ — скінченна множина станів автомата
  • ${\displaystyle s\in K}$ — єдиний допустимий початковий стан автомата
  • ${\displaystyle F\subset K}$ — множина дозволених кінцевих станів, причому допускається F=Ø, і F=K
• ${\displaystyle \Sigma }$ — скінченна множина символів вхідного алфавіту, з якого формуються рядки, що зчитуються автоматом
• ${\displaystyle S}$ — алфавіт пам'яті (магазину чи стеку)
  • ${\displaystyle m\in S}$ — нульовий символ пам'яті.
• ${\displaystyle \pi }$ — функція переходів: ${\displaystyle \pi :K\times \Sigma \times S\rightarrow K\times S}$

Пам'ять працює як стек, тобто для зчитування доступний лише останній записаний в ній елемент. Функція переходу за комбінацією поточного стану, вхідного символу і символу на вершині магазину визначає наступний стан (і, можливо, символ для запису в магазин). У випадку, коли в правій частині автоматного правила присутній ${\displaystyle e}$, у магазин нічого не додається, а елемент з вершини стирається. Якщо магазин порожній, то спрацьовують правила з ${\displaystyle e}$ в лівій частині.

Автомат з магазинною пам'яттю може розпізнати будь-яку контекстно-вільну мову.

У чистому вигляді автомати з магазинною пам'яттю використовуються вкрай рідко. Зазвичай ця модель використовується для наочного подання відмінності звичайних скінченних автоматів від синтаксичних граматик. Реалізація автоматів з магазинною пам'яттю відрізняється від кінцевих автоматів тим, що поточний стан автомата сильно залежить від будь-якого попереднього.