Абстрактний автомат (в теорії алгоритмів) - математична абстракція, модель дискретного пристрою, що має один вхід, один вихід і в кожен момент часу знаходиться в одному стані з безлічі можливих. На вхід цього пристрою надходять символи однієї мови, на виході воно видає символи (в загальному випадку) іншої мови.
Формально абстрактний автомат визначається як п'ятірка
Де S - кінцеве безліч станів автомата, X, Y - кінцеві вхідний і вихідний алфавіти відповідно, з яких формуються рядки, зчитувальні і видаються автоматом, - функція переходів, - функція виходів.
Абстракний автомат з виділеним початковим станом називається ініціальним автоматом. Таким чином, абстрактний автомат визначає сімейство ініціальних автоматовЕслі функції переходів і виходів однозначно визначені для кожної пари то автомат називають детермінованим. В іншому випадку автомат називають недетермінованим або частково певним.
Якщо функція переходів і / або функція виходів є випадковими, то автомат називають імовірнісним.
Обмеження числа параметрів абстрактного автомата визначило таке поняття як кінцевий автомат.
Функціонування автомата полягає в породженні двох послідовностей: послідовності чергових станів автоматапоследовательності вихідних символів які для послідовності сімволовразворачіваются в моменти дискретного часу t = 1, 2, 3, ... Моменти дискретного часу отримали назву тактів.
Функціонування автомата в дискретні моменти часу t може бути описано системою рекурентних співвідношень:
Для уточнення властивостей абстрактних автоматів введена класифікація.
Абстрактні автомати утворюють фундаментальний клас дискретних моделей як самостійна модель, і як основна компонента машин Тьюринга, автоматів з магазинної пам'яттю, кінцевих автоматів та інших перетворювачів інформації.
Модель абстрактного автомата широко використовується, як базова, для побудови дискретних моделей розпізнають, що породжують і перетворюють послідовності символів.