Стр. 42 - Информационные структуры и их преобразование

40 Содержание
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
Операции над магазином:
- выбрать символ из магазина;
- заслать в магазин;
- оставить в магазине без изменения.
Операции над состоянием:
- оставить в прежнем состоянии;
- перейти в новое состояние.
-
Операции над входной цепочкой:
- перейти к следующему входному символу;
- остаться на прежнем символе.
Обработку входной цепочки МП-автомат начинает в некотором
выделенном состоянии при определённом содержимом магазина.
Сканируемый символ является первым символом входной цепочки, затем
автомат выполняет операции, задаваемые ему управляющим устройством.
Автомат не должен требовать следующий входной символ, если текущий
символ стека - концевой маркер (магазин пуст).
Автомат задаётся:
- конечным множеством входных символов;
- конечным множеством магазинных символов, включая маркер;
- некоторой функцией, обеспечивающей переход из одного
состояния в другое.
Переход выполняется операцией над магазином, входом и состоянием.
Цепочка символов входного алфавита допускается распознавателем, если над
действием этой цепочки начать работу в некотором выделенном состоянии и
с начальным содержимым магазина и делать последовательность переходов,
попадая в заключительное состояние, при котором магазин пуст. Таким
образом, МП - автомат есть семёрка символов:
МП={Q, Σ , Г, δ , q0, Г0 , F};
Q - множество состояний;
Σ - входной алфавит;
Г - алфавит магазинных символов;
δ - функция отображения, обеспечивающая преобразование:
* * Г Q Г Q × → ×Σ×;
q 0- начальное состояние;
Г 0- начальный символ магазина;