65. Распознаватель скобочных выражений
Рассмотрим одну из возможных реализация АМП, для задачи проверки корректности вложенности круглых скобок. Кратко опишем общий принцип работы автомата. Если входная головка читает "(", то в магазин заталкивается символ А. Если входная головка читает ")", то из магазина выталкивается содержащийся там символ. Цепочка отвергается, если:
1. На входе остаются правые скобки, а магазин пуст.
2. Входная цепочка прочитана до конца, а в магазине остаются символы А, соответствующие левым скобкам, для которых не нашлось пары.
Определим данный АМП следующим образом:
Множество входных символов: { (, ), }.
Множество магазинных символов: { A, }
Множество состояний: t, где t является также и начальным состоянием автомата, раз оно единственное.
Переходы:
1. (, A, S А, S,
- (, , S А, S,
- ), A, S , S,
- ), , S Отвергнуть
- , A, S Отвергнуть
- , , S Допустить
В начальном состоянии магазин содержит только маркер дна ( ).
Из представленного описания видно, что поведение автомата имитирует ранее рассмотренный метод распознавания с использованием счетчика. Только вместо счетчика используются "палочки" (раньше с помощью палочек учили считать в школе). Эти палочки могут записываться в стек и стираться из него, отражая разность между прочитанными открывающимися и закрывающимися скобками. Работу данного АМП можно рассмотреть на примере распознавания нескольких цепочек. Пусть, первая цепочка будет иметь следующий вид:
( ( ) ( ) )
| 