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

(МП-автоматы)

Есть «промежуточная» математическая модель между автоматами и контекстно-свободными грамматиками – автомат с магазинной памятью. (МП-автомат).

Существует достаточно распространенная задача – задача определения парности скобок. Однако ее нельзя представить автоматной грамматикой.

Соответсвующая грамматика может выглядеть следующим образом:

S®(S)

S®SS

S®e

МП-автомат состоит из входной ленты, в ячейках которой записывается анализируемая строка (┤-конец строки), устройства управления и разбитого на ячейки магазина (стека). Ñ - символ пустого магазина. Устройство управления автомата может)."помнить" состояние (S1…).

Требуется распознать: (() ())

(() ()) ┤

Ñ

Работу автомата можно описать программой.

S1	X	Ñ
(	¯ X ®	¯ X ®
)	­®	¾
┤	¾	+

Здесь и далее используются обозначения:

¯a - поместить строку a в вершину магазина.

a - заменить верхний символ магазина на строку a.

­a - убрать символ из вершины магазина.

® - сдвинуться на шаг вправо по входной строке.

> < - стоять на месте.

¾ - отвергнуть.

+ - принять.

S - State - состояние МП-автомата (на каждое состояние своя таблица, здесь одно состояние S1).

Ñ [S1] (() ()) ┤

­

xÑ [S1] (() ()) ┤

­

xxÑ [S1] (() ()) ┤

­

xÑ [S1] (() ()) ┤

­

xxÑ [S1] (() ()) ┤

­

xÑ [S1] (() ()) ┤

­

Ñ [S1] (() ()) ┤

­

Задача распознавания вложенных скобок "типа матрешка" сложнее и для ее распознавания требуется МП-автомат с двумя состояниями:

((()))

S2	X	Ñ
(	¾	¾
)	S2 ­®	¾
┤	¾	+

S1	X	Ñ
(	S1¯ X ®	S1¯ X ®
)	S2 ­®	¾
┤	¾	+

При встрече первой закрывающей скобки МП автомат меняет состояние S₁ на состояние S₂.