64.Организация автомата с магазинной памятью
АМП в качестве рабочей памяти использует стек, называемый также магазином. Данная память поддерживает только ограниченные операции доступа, в то же время достаточные для решения сложных задач, включая и задачи распознавания цепочек. Автомат с магазинной памятью определяется следующими пятью объектами:
1. Конечным множеством входных символов, включающим концевой маркер ( ).
- Конечным множеством магазинных символов, включающим маркер дна ( ).
- Конечным множеством состояний, включающим начальное состояние.
- Устройством управления (УУ), которое каждой комбинации входного символа, магазинного символа и состояния ставит в соответствие выход или переход. Переход, в отличие от выхода, заключается в выполнении операций над магазином, состоянием и входом. Операции, запрашивающие входной символ после концевого маркера или выталкивания из магазина после маркера дна, а также операция вталкивания маркера дна, исключаются.
- Начальным содержимым магазина, содержащим маркер дна и, возможно пустую, цепочку магазинных символов.
Автомат с магазинной памятью называется распознавателем, если у него 2 выхода: "Допустить" и "Отвергнуть".
Операции автомата
Динамическое поведение АМП описывается через его операциями над входной цепочкой и стеком, а также переходами из одного состояния в другое. К операциям над стеком относятся:
1. "Вытолкнуть" - выталкивает из стека верхний символ (будем также использовать сокращенное обозначение " ").
- "Втолкнуть А" - вталкивает в стек магазинный символ А (будем также использовать сокращенное обозначение " А").
- "Заменить XYZ" - используется для сокращения записи, когда необходимо вытолкнуть верхний символ и вместо него втолкнуть несколько других (в данном случае X, Y, Z). Эквивалентна:
X Y Z (сокращенно обозначим: XYZ).
Переход АМП из одного состояния в другое указывается явно операцией "Состояние t", где t - новое состояние автомата (будем сокращать текст данной операции до "[t]").
Сдвиг входной головки на один символ вправо относительно входной ленты задается операцией "Сдвиг" (сократим до " "). После ее выполнения текущим символом становится следующий символ на входной ленте. Другой операцией над входной головкой является "Держать", которая не изменяет положение входной головки до следующего шага (можно просто не писать, если нет сдвига).
Переход или шаг автомата - это выполнение операций над стеком и входной головкой, а также изменение состояния. При этом необязательно, чтобы за один шаг происходили все изменения. Возможно: или входная головка останется на месте, или не произойдет операции над стеком, или не изменится состояние.
| 