Перегляд вихідного коду сторінки Автомат з магазинною пам'яттю

{{Теорія автоматів}}
'''Автома́т з магази́нною па́м'яттю''' ({{lang-en|pushdown automaton}})&nbsp;— в [[Теорія автоматів|теорії автоматів]] — [[скінченний автомат]], що додатково використовує [[стек]] для зберігання станів.

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

* <math>K</math>&nbsp;— [[скінченна множина]] станів автомата
** <math> s \in K</math>&nbsp;— єдиний допустимий початковий стан автомата
** <math>F \subset K</math>&nbsp;— множина дозволених кінцевих станів, причому допускається F=Ø, і F=K
* <math>\Sigma</math>&nbsp;— скінченна множина символів вхідного алфавіту, з якого формуються рядки, що зчитуються автоматом
* <math>S</math>&nbsp;— алфавіт пам'яті (магазину чи стеку)
** <math>m \in S</math>&nbsp;— нульовий символ пам'яті.
* <math>\pi</math>&nbsp;— функція переходів: <math>\pi : K \times \Sigma \times S \rightarrow K \times S</math>

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

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

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

== Види автоматів з магазинної пам'яттю ==

Існують детерміновані та недетерміновані автомати з магазинною пам'яттю. Для недетермінованих автоматів (на відміну від детермінованих) існує два еквівалентні критерії завершення роботи:
* порожній магазин
* досягнення кінцевого стану
[[Детермінований автомат]] завершує роботу лише тоді, коли досягає кінцевого стану.

== Примітки ==
{{reflist}}

== Джерела ==
* {{книга
|автор        = [[Гаврилків Володимир Михайлович|Гаврилків В. М.]]
|назва        = Формальні мови та алгоритмічні моделі
|рік          = 2023
|видавництво  = Голіней
|місто        = {{Comment|І.-Ф. |Івано-Франківськ}}
|сторінок     = 180
|мова         = uk
}}
* {{Cinderella Book}}
* {{Роджерс.Теорія рекурсивних функцій}}

{{Math-stub}}

[[Категорія:Теорія автоматів]]
[[Категорія:Моделі обчислень]]