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

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

Содержание [убрать]

1 Формальное определение
2 Пример с использованием автомата с магазинной памятью
3 Виды автоматов с магазинной памятью
4 Литература

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

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

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

где

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

Память работает как стек, то есть для чтения доступен последний записанный в неё элемент. Таким образом, функция перехода является отображением . То есть, по комбинации текущего состояния, входного символа и символа на вершине магазина автомат выбирает следующее состояние и, возможно, символ для записи в магазин. В случае, когда в правой части автоматного правила присутствует e, в магазин ничего не добавляется, а элемент с вершины стирается. Если магазин пуст, то срабатывают правила с e в левой части.

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

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

12 Следующая ⇒