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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Формальное определение[править | править вики-текст]

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

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

\boldsymbol{M = (K , \Sigma , \pi , s , F, S, m)} где

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

Память работает как стек, то есть для чтения доступен последний записанный в неё элемент. Таким образом, функция перехода является отображением \pi : K \times \Sigma \times S \rightarrow K \times S. То есть, по комбинации текущего состояния, входного символа и символа на вершине магазина автомат выбирает следующее состояние и, возможно, символ для записи в магазин. В случае, когда в правой части автоматного правила присутствует 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. достижение конечного состояния

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

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

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