Абстра́ктный автома́т (в теории алгоритмов) — математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. На вход этому устройству поступают символы одного языка, на выходе оно выдаёт символы (в общем случае) другого языка.
Формально абстрактный автомат определяется как пятерка
A=(S,X,Y,δ,λ){displaystyle {boldsymbol {A=(S,X,Y,delta ,lambda )}}}
Где S — конечное множество состояний автомата, X, Y — конечные входной и выходной алфавиты соответственно, из которых формируются строки, считываемые и выдаваемые автоматом, δ:S×X→S{displaystyle delta :Stimes Xrightarrow S} — функция переходов, λ:S×X→Y{displaystyle lambda :Stimes Xrightarrow Y} — функция выходов.
Функциональная схема абстрактного автомата
Абстракный автомат с выделенным начальным состоянием называется инициальным автоматом. Таким образом, абстрактный автомат определяет семейство инициальных автоматов
(si,A),si∈S{displaystyle {boldsymbol {(s_{i},A),s_{i}in S}}}
Для уточнения свойств абстрактных автоматов введена классификация.
Абстрактные автоматы образуют фундаментальный класс дискретных моделей как самостоятельная модель, и как основная компонента машин Тьюринга, автоматов с магазинной памятью, конечных автоматов и других преобразователей информации.
Модель абстрактного автомата широко используется, как базовая, для построения дискретных моделей распознающих, порождающих и преобразующих последовательности символов.
