Автомат с магазинной памятью

В теории автоматов, автомат с магазинной памятью — это конечный автомат, который использует стек для хранения состояний.

Формальное определениеПравить

 

Диаграмма автомата с магазинной памятью

В отличие от обычных конечных автоматов, автомат с магазинной памятью является набором

$M=(K,\mathrm{\Sigma <!--\; \Sigma \; -->},\mathrm{\pi <!--\; \pi \; -->},s,F,S,e),$$M=(K,\Sigma ,\pi ,s,F,S,e),$ 

где

K — конечное множество состояний автомата,

$s\in <!--\; \in \; -->K$$s\in K$  — единственно допустимое начальное состояние автомата,

$F\subseteq <!--\; \subseteq \; -->K$$F\subseteq K$  — множество конечных состояний, причём допустимо F=Ø и F=K,

Σ — допустимый входной алфавит, из которого формируются строки, считываемые автоматом,

S — алфавит памяти (магазина),

$e\in <!--\; \in \; -->S$$e\in S$  — нулевой символ памяти.

Память работает как стек, то есть для чтения доступен последний записанный в неё элемент. Таким образом, функция перехода является отображением $\mathrm{\pi <!--\; \pi \; -->}:K\times <!--\; \times \; -->\mathrm{\Sigma <!--\; \Sigma \; -->}\times <!--\; \times \; -->S\to <!--\; \to \; -->K\times <!--\; \times \; -->S$$\pi :K\times \Sigma \times S\to K\times S$ . То есть, по комбинации текущего состояния, входного символа и символа на вершине магазина автомат выбирает следующее состояние и, возможно, символ для записи в магазин. В случае, когда в правой части автоматного правила присутствует $e$$e$ , в магазин ничего не добавляется, а элемент с вершины стирается. Если магазин пуст, то срабатывают правила с $e$$e$  в левой части.

Класс языков, распознаваемых автоматами с магазинной памятью, совпадает с классом контекстно-свободных языков.

В чистом виде автоматы с магазинной памятью используются крайне редко. Обычно эта модель используется для наглядного представления отличия обычных конечных автоматов от синтаксических грамматик. Реализация автоматов с магазинной памятью отличается от конечных автоматов тем, что текущее состояние автомата сильно зависит от любого предыдущего.

Пример с использованием автомата с магазинной памятьюПравить

repeat X := верхний символ магазина;
  if X = терминал или $
  then
    if X = InSym
    then
      удалить X из магазина;
      InSym := очередной символ;
    else
      error()
    end
  else /* X = нетерминал */
    if M[X, InSym] = X->Y1Y2...Yk
    then
      удалить X из магазина;
      поместить Yk, Yk-1, ..., Y1 в магазин
      (Y1 на верхушку);
      вывести правило X->Y1Y2...Yk
    else
      error() /* вход таблицы M пуст */
    end
  end
until X = $ /* магазин пуст */

Виды автоматов с магазинной памятьюПравить

Существуют детерминированные и недетерминированные автоматы с магазинной памятью.

Для недетерминированных автоматов (в отличие от детерминированных) существует два эквивалентных критерия завершения работы:

1. пустой магазин,
2. достижение конечного состояния.

Детерминированный автомат завершает работу лишь тогда, когда достигает конечного состояния.

См. такжеПравить

• JFLAP — кроссплатформенная программа симулятор автоматов, машины Тьюринга, грамматик, рисует граф автомата.

ЛитератураПравить

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