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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

Пам'ять працює як стек, тобто для читання доступний останній записаний в неї елемент. Таким чином, функція переходу є відображенням \pi : K \times \Sigma \times S \rightarrow K \times S. Тобто, по комбінації поточного стану, вхідного символу і символу на вершині магазину автомат вибирає наступний стан і, можливо, символ для запису в магазин. У випадку, коли у правій частині автоматного правила присутній e, в магазин нічого не додається, а елемент з вершини стирається. Якщо магазин порожній, то спрацьовують правила з e в лівій частині.

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

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

Види автоматів з магазинної пам'яттю[ред.ред. код]

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

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

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

Джерела[ред.ред. код]

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