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

Комбінаційна логікаСкінчений автоматАвтомат з магазинною пам'яттюМашина ТюрінгаТеорія автоматівAutomata theory ua.svg
Опис зображення
Класи автоматів (Clicking on each layer gets an article on that subject)

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

На відміну від скінченних автоматів, автомат з магазинною пам'яттю формально визначається як набір
, де

  •  — скінченна множина станів автомата
    •  — єдиний допустимий початковий стан автомата
    •  — множина дозволених кінцевих станів, причому допускається F=Ø, і F=K
  •  — скінченна множина символів вхідного алфавіту, з якого формуються рядки, що зчитуються автоматом
  •  — алфавіт пам'яті (магазину чи стеку)
    •  — нульовий символ пам'яті.
  •  — функція переходів:

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

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

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

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

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

  • порожній магазин
  • досягнення кінцевого стану

Детермінований автомат завершує роботу лише тоді, коли досягає кінцевого стану.

ДжерелаРедагувати

ЛітератураРедагувати

  • Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1