Абстрактный автомат

Абстра́ктный автома́т (в теории алгоритмов) — математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. На вход этому устройству поступают символы одного языка, на выходе оно выдаёт символы (в общем случае) другого языка.

Абстрактный автомат

Формально абстрактный автомат определяется как пятерка

${\displaystyle {\boldsymbol {A=(S,X,Y,\delta ,\lambda )}}}$

Где S - конечное множество состояний автомата, X, Y - конечные входной и выходной алфавиты соответственно, из которых формируются строки, считываемые и выдаваемые автоматом, ${\displaystyle \delta :S\times X\rightarrow S}$ - функция переходов, ${\displaystyle \lambda :S\times X\rightarrow Y}$ - функция выходов.

Функциональная схема абстрактного автомата

Абстракный автомат с выделенным начальным состоянием называется инициальным автоматом. Таким образом, абстрактный автомат определяет семейство инициальных автоматов

${\displaystyle {\boldsymbol {(s_{i},A),s_{i}\in S}}}$

Для уточнения свойств абстрактных автоматов введена классификация.

Абстрактные автоматы образуют фундаментальный класс дискретных моделей как самостоятельная модель, и как основная компонента машин Тьюринга, автоматов с магазинной памятью, конечных автоматов и других преобразователей информации.

Модель абстрактного автомата широко используется, как базовая, для построения дискретных моделей распознающих, порождающих и преобразующих последовательности символов.