Анотація: У даній лекції розглядаються автомати з магазинною пам'яттю, в яких крім обмеженою пам'яті, що зберігає поточний стан, є потенційно нескінченна пам'ять, яка використовується як магазин. Даються необхідні визначення, і доводиться, що автомати з магазинною пам'яттю розпізнають в точності контекстно-вільні мови. Наведені приклади практичного використання автоматів з магазинної пам'яттю і наведені вправи для самостійного опрацювання
Подібно до того, як праволінейним граматика відповідають кінцеві автомати, контекстно-вільним граматика відповідають автомати з магазинною пам'яттю (МП-автомати). В такому автоматі, крім обмеженою пам'яті, що зберігає поточний стан, є потенційно нескінченна пам'ять, яка використовується як стек (магазин), тобто структура даних, де в кожен момент доступний тільки той елемент, який був доданий пізніше за інших присутніх на даний момент елементів.
Для наочності стек зазвичай зображують вертикально, так, що доступний елемент даних (вершина) знаходиться нагорі. Але при формальному визначенні конфігурації (миттєвого стану) МП-автомата зручно вважати весь вміст стека кінцевої послідовністю символів, тобто словом (в алфавіті, в якому перераховані всі можливі дані, "уміщаються" в одній комірці стека). Перш ніж визначити конфігурацію, доведеться прийняти довільне угоду про те, в якому порядку записувати вміст стека в цьому слові. У цій книзі вважається, що вершина стека знаходиться на початку слова (тобто зліва). У розділі 10.1 даються необхідні визначення. У розділі 10.2 доводиться, що МП-автомати розпізнають в точності контекстно-вільні мови.
10.1. Визначення автомата з магазинної пам'яттю
Визначення 10.1.1. Автомат з магазинної пам'яттю (МП-автомат, магазинний автомат, стековий автомат, pushdown automaton) - це шістка 
, де 
, 
, 
і 
- кінцеві безлічі, 
, 
і
Тут Q - безліч станів, - вхідний алфавіт, - алфавіт магазинної пам'яті (stack alphabet), - безліч переходів (transition relation), елементи I називаються початковими станами, елементи F - заключними або допускають станами.
Приклад 10.1.2. Нехай Q = {1,2}, 
, 
,
, 
. тоді 
- МП-автомат.
Зауваження 10.1.3. МП-автомати можна зображувати у вигляді діаграм станів. На діаграмі кожне стан позначається кружком, а перехід - стрілкою. Кожне початковий стан розпізнається по провідній в нього короткою стрілкою. Кожне допускає стан відзначається на діаграмі подвійним кружком. Стрілка з позначкою 
, Яка веде з p в q, показує, що 
є переходом даного МП-автомата.
Приклад 10.1.4. Нижче приведена діаграма МП-автомата з прикладу 10.1.2.
Визначення 10.1.5. Конфігурацією МП-автомата називається будь-яка трійка 
, де 
, 
, 
.
Визначення 10.1.6. Визначимо на множині всіх конфігурацій МП-автомата бінарне відношення 
(Такт роботи) наступним чином. якщо 
, і , то 
.
Зауваження 10.1.7 Зазвичай з контексту ясно, про яке МП-автоматі йде мова. тоді замість будемо писати 
.
Приклад 10.1.8. Для МП-автомата з прикладу 10.1.2 виконується 
і 
.
Визначення 10.1.9. бінарне відношення 
визначається як рефлексивне, транзитивне замикання відношення .
Приклад 10.1.10. Для МП-автомата з прикладу 10.1.2 виконується 
і 
.
Лемма 10.1.11. якщо 
і 
, то 
.
Доказ. Лему легко довести індукцією за кількістю тактів в обчислювальному процесі, що веде з конфігурації 
в конфігурацію 
.
Визначення 10.1.12. слово 
допускається МП-автоматом , Якщо знайдуться такі стани 
і 
, що 
.
Визначення 10.1.13. Мова, розпізнається МП-автоматом, - безліч всіх слів, що допускаються цим МП-автоматом. Мова, розпізнається МП-автоматом M, позначається L (M).
Зауваження 10.1.14. Зазвичай в підручниках використовується більш вузьке визначення МП-автомата, але це не змінює класу мов, які розпізнаються МП-автоматами.
Приклад 10.1.15. нехай 
- МП-автомат з прикладу 10.1.2. тоді 
.
Приклад 10.1.16. нехай 
. Розглянемо МП-автомат 
, де 
, , I = {1}, F = {4,5} і
тоді 
.
Визначення 10.1.17. Два МП-автомата еквівалентні, якщо вони розпізнають один і той же мова.
Зауваження 10.1.18. В даному посібнику не розглядаються перетворювачі з магазинної пам'яттю (pushdown transducer) узагальнення автоматів з магазинної пам'яттю за допомогою додавання "вихідного" потоку (див. [7, 3.5] або [2, 3.1.4] ).
Зауваження 10.1.19. Деякі автори змінюють визначення допустимих слів наступним чином: слово w допускається МП-автоматом , Якщо знайдуться такі стани і і послідовність , що 
. Таке визначення не змінює класу мов, які розпізнаються МП-автоматами.
Зауваження 10.1.20. Деякі автори додають в визначення МП-автомата сьому компоненту - Z0, звану маркером магазинної пам'яті (start pushdown symbol), і змінюють визначення допустимих слів наступним чином: слово w допускається МП-автоматом 
, Якщо знайдуться такі стани і , що 
. Таке визначення не змінює класу мов, які розпізнаються МП-автоматами.
Зауваження 10.1.21. Клас мов, які розпізнаються МП-автоматами, не зміниться також, якщо використовувати наступну природну комбінацію двох попередніх визначень: слово w допускається МП-автоматом , Якщо знайдуться такі стани і і послідовність , що 
.
Зауваження 10.1.22. Деякі автори додають в визначення МП-автомата маркер магазинної пам'яті Z0, відкидають безліч F і змінюють визначення допустимих слів наступним чином: слово w допускається МП-автоматом 
, Якщо знайдуться такі стани і , що . Це також не змінює класу мов, які розпізнаються МП-автоматами.
Вправа 10.1.23. Знайти МП-автомат, що розпізнає мову 
Вправа 10.1.24. Знайти МП-автомат, що розпізнає мову 
Вправа 10.1.25. Знайти МП-автомат, що розпізнає мову 
