Русская Википедия:Автомат с магазинной памятью
В теории автоматов, автомат с магазинной памятью — это конечный автомат, который использует стек для хранения состояний.
Формальное определение
В отличие от обычных конечных автоматов, автомат с магазинной памятью является наборомШаблон:Sfn
- <math>M = (K, \Sigma, \pi, s, F, S, e),</math>
где
- K — конечное множество состояний автомата,
- <math>s \in K</math> — единственно допустимое начальное состояние автомата,
- <math>F \subseteq K</math> — множество конечных состояний, причём допустимо F=Ø и F=K,
- Σ — допустимый входной алфавит, из которого формируются строки, считываемые автоматом,
- S — алфавит памяти (магазина),
- <math>e \in S</math> — нулевой символ памяти.
Память работает как стек, то есть для чтения доступен последний записанный в неё элемент. Таким образом, функция перехода является отображением <math>\pi : K \times \Sigma \times S \to K \times S</math>. То есть, по комбинации текущего состояния, входного символа и символа на вершине магазина автомат выбирает следующее состояние и, возможно, символ для записи в магазин. В случае, когда в правой части автоматного правила присутствует <math>e</math>, в магазин ничего не добавляется, а элемент с вершины стирается. Если магазин пуст, то срабатывают правила с <math>e</math> в левой части.
Класс языков, распознаваемых автоматами с магазинной памятью, совпадает с классом контекстно-свободных языков.
В чистом виде автоматы с магазинной памятью используются крайне редко. Обычно эта модель используется для наглядного представления отличия обычных конечных автоматов от синтаксических грамматик. Реализация автоматов с магазинной памятью отличается от конечных автоматов тем, что текущее состояние автомата сильно зависит от любого предыдущего.
Пример с использованием автомата с магазинной памятью
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 = $ /* магазин пуст */
Виды автоматов с магазинной памятью
Существуют детерминированные и недетерминированные автоматы с магазинной памятью.
Для недетерминированных автоматов (в отличие от детерминированных) существует два эквивалентных критерия завершения работы:
- пустой магазин,
- достижение конечного состояния.
Детерминированный автомат завершает работу лишь тогда, когда достигает конечного состояния.
См. также
- JFLAP — кроссплатформенная программа симулятор автоматов, машины Тьюринга, грамматик, рисует граф автомата.
Примечания
Литература
Шаблон:Формальные языки Шаблон:Math-stub
