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

---

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

где ${\displaystyle Q}$ — множество состояний автомата, A, B — входной и выходной алфавиты соответственно, из которых формируются строки, считываемые и выдаваемые автоматом, ${\displaystyle \varphi :Q\times A\rightarrow Q}$ — функция переходов, ${\displaystyle \lambda :Q\times A\rightarrow B}$ — функция выходов.^[2]

Абстрактный автомат с конечными множествами ${\displaystyle A,B,Q}$ называется конечным автоматом.^[3] Если же одно из этих множеств является бесконечным, то такой автомат называется бесконечным автоматом.^[4]

Функционирование автомата состоит в том, что по заданной входной последовательности и из заданного начального состояния автомат однозначно выдаёт две последовательности: последовательность состояний автомата ${\displaystyle q:\mathbb {N} \to Q}$ и последовательность выходных символов ${\displaystyle b:\mathbb {N} \to B}$. Номера элементов этих последовательностей интерпретируются как дискретные моменты времени и называются также тактами. Эти последовательности определяются рекурсивно при помощи следующих уравнений, называемых каноническими уравнениями автомата:

${\displaystyle a:\mathbb {N} \to A}$ здесь последовательность входных символов, ${\displaystyle q_{1}\in Q}$ — начальное состояние. Абстрактный автомат с выделенным начальным состоянием называется инициальным автоматом.^[5] Такой автомат обычно обозначается ${\displaystyle V_{q_{1}}}$.

---