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

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

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

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

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

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

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

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