Абстрактный автомат
Материал из Википедии — свободной encyclopedia
Абстра́ктный автома́т — в дискретной математике математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. На вход этому устройству поступают символы одного алфавита, на выходе оно выдаёт символы (в общем случае) другого алфавита.[1]
![Thumb image](http://upload.wikimedia.org/wikipedia/ru/thumb/c/c0/%D0%90%D0%B1%D1%81%D1%82%D1%80%D0%B0%D0%BA%D1%82%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82.jpg/220px-%D0%90%D0%B1%D1%81%D1%82%D1%80%D0%B0%D0%BA%D1%82%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82.jpg)
Формально абстрактный автомат определяется как пятёрка
,
где — множество состояний автомата, A, B — входной и выходной алфавиты соответственно, из которых формируются строки, считываемые и выдаваемые автоматом,
— функция переходов,
— функция выходов.[2]
![Thumb image](http://upload.wikimedia.org/wikipedia/ru/thumb/3/31/%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%BE%D0%BD%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D1%85%D0%B5%D0%BC%D0%B0_%D0%B0%D0%B1%D1%81%D1%82%D1%80%D0%B0%D0%BA%D1%82%D0%BD%D0%BE%D0%B3%D0%BE_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%B0.jpg/320px-%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%BE%D0%BD%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D1%85%D0%B5%D0%BC%D0%B0_%D0%B0%D0%B1%D1%81%D1%82%D1%80%D0%B0%D0%BA%D1%82%D0%BD%D0%BE%D0%B3%D0%BE_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%B0.jpg)
Абстрактный автомат с конечными множествами называется конечным автоматом.[3] Если же одно из этих множеств является бесконечным, то такой автомат называется бесконечным автоматом.[4]
Функционирование автомата состоит в том, что по заданной входной последовательности и из заданного начального состояния автомат однозначно выдаёт две последовательности: последовательность состояний автомата и последовательность выходных символов
. Номера элементов этих последовательностей интерпретируются как дискретные моменты времени и называются также тактами. Эти последовательности определяются рекурсивно при помощи следующих уравнений, называемых каноническими уравнениями автомата:
где \phi – функция переходов, \psi – функция выходов.
здесь последовательность входных символов,
— начальное состояние. Абстрактный автомат с выделенным начальным состоянием называется инициальным автоматом.[5] Такой автомат обычно обозначается
.
Допускается также рассмотрение конечной последовательности входных символов ; в таком случае длина выходной последовательности
будет такая же, как и длина
, а длина
на
больше. Говорят, что инициальный автомат
задаёт функцию
, если для входной последовательности
автомат выдаёт выходную последовательность
. Множество функций, задаваемых всевозможными инициальными автоматами со входным алфавитом
и выходным алфавитом
, есть в точности множество детерминированных функций из
в
.
Автомат с выделенным множеством конечных состояний называется терминальным автоматом.
Для уточнения свойств абстрактных автоматов введена классификация.
Абстрактные автоматы образуют фундаментальный класс дискретных моделей как самостоятельная модель, и как основная компонента машин Тьюринга, автоматов с магазинной памятью, конечных автоматов и других преобразователей информации.
Модель абстрактного автомата широко используется как базовая для построения дискретных моделей автоматов, распознающих, порождающих и преобразующих последовательности символов.