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

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

${\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}}}$

Если функции переходов и выходов однозначно определены для каждой пары ${\displaystyle {\boldsymbol {(s,x)\in S\times X}}}$ , то автомат называют детерминированным. В противном случае автомат называют недетерминированным или частично определённым.

Если функция переходов и/или функция выходов являются случайными, то автомат называют вероятностным .

Ограничение числа состояний абстрактного автомата определило такое понятие как конечный автомат .

Функционирование автомата состоит в порождении двух последовательностей: последовательности очередных состояний автомата ${\displaystyle {\boldsymbol {s_{1}[1]s_{2}[2]s_{3}[3]...}}}$ и последовательности выходных символов ${\displaystyle {\boldsymbol {y_{1}[1]y_{2}[2]y_{3}[3]...}}}$ , которые для последовательности символов ${\displaystyle {\boldsymbol {x_{1}[1]x_{2}[2]x_{3}[3]...}}}$ разворачиваются в моменты дискретного времени t = 1, 2, 3, … Моменты дискретного времени получили название тактов.

Функционирование автомата в дискретные моменты времени t может быть описано системой рекуррентных соотношений: ${\displaystyle {\boldsymbol {s(t+1)=\delta (s(t),x(t));}}}$

${\displaystyle {\boldsymbol {y(t)=\lambda (s(t),x(t)).}}}$

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

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

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

Литература

• Виктор Михайлович Глушков . Абстрактная теория автоматов. — Успехи математических наук , т. XVI, вып. 5 (101). — М. , 1961. — С. 476.

• Виктор Михайлович Глушков . Синтез цифровых автоматов. — М. : Государственное издательство физико-математической литературы , 1962. — С. 476.