Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
(МП-автоматы)
Есть «промежуточная» математическая модель между автоматами и контекстно-свободными грамматиками – автомат с магазинной памятью. (МП-автомат).
Существует достаточно распространенная задача – задача определения парности скобок. Однако ее нельзя представить автоматной грамматикой.
Соответсвующая грамматика может выглядеть следующим образом:
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.
Дата публикования: 2014-11-03; Прочитано: 380 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!