Специальная математика. Соловьев А.Е. - 81 стр.

                                   const

             7.10. Детерминированные автоматы с магазинной памятью
                                       (МП-автоматы)

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

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

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

     ( ( )    ( )   ) ┤

                               


Работу автомата можно описать программой.
                                           S1
 S1      X      
 (       X     X
              
 )           
 ┤             +

Здесь и далее используются обозначения:
 - поместить строку  в вершину магазина.
  - заменить верхний символ магазина на строку .

 - убрать символ из вершины магазина.
 - сдвинуться на шаг вправо по входной строке.
> < - стоять на месте.
 - отвергнуть.
+ - принять.
S - State - состояние МП-автомата (на каждое состояние своя таблица, здесь одно состояние
S1).

   [S1] ( ( ) ( ) ) ┤
         


                                                — 81 —