Лекция: Детерминированные автоматы с магазинной памятью
(МП-автоматы)
Есть «промежуточная» математическая модель между автоматами и контекстно-свободными грамматиками – автомат с магазинной памятью. (МП-автомат).
Существует достаточно распространенная задача – задача определения парности скобок. Однако ее нельзя представить автоматной грамматикой.
Соответсвующая грамматика может выглядеть следующим образом:
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 ® | ¾ |
| ┤ | ¾ | + |
При встрече первой закрывающей скобки МП автомат меняет состояние S1 на состояние S2.