Формально абстрактный автомат определяется как пятёрка
<math>\boldsymbol{A = (S, X, Y, \delta, \lambda)}</math>
Где S — конечное множество состояний автомата, X, Y — конечные входной и выходной алфавиты соответственно, из которых формируются строки, считываемые и выдаваемые автоматом, <math>\delta : S \times X \rightarrow S</math> — функция переходов, <math>\lambda : S \times X \rightarrow Y</math> — функция выходов.
Абстрактный автомат с выделенным начальным состоянием называется инициальным автоматом. Таким образом, абстрактный автомат определяет семейство инициальных автоматов
<math>\boldsymbol{(s_i, A), s_i \in S}</math>
Если функции переходов и выходов однозначно определены для каждой пары <math>\boldsymbol{(s, x) \in S \times X}</math>, то автомат называют детерминированным. В противном случае автомат называют недетерминированным или частично определённым.
Если функция переходов и/или функция выходов являются случайными, то автомат называют вероятностным.
Ограничение числа состояний абстрактного автомата определило такое понятие как конечный автомат.
Функционирование автомата состоит в порождении двух последовательностей: последовательности очередных состояний автомата <math>\boldsymbol{s_1[1]s_2[2]s_3[3]...}</math> и последовательности выходных символов <math>\boldsymbol{y_1[1]y_2[2]y_3[3]...}</math>, которые для последовательности символов <math>\boldsymbol{x_1[1]x_2[2]x_3[3]...}</math> разворачиваются в моменты дискретного времени t = 1, 2, 3, … Моменты дискретного времени получили название тактов.
Функционирование автомата в дискретные моменты времени t может быть описано системой рекуррентных соотношений:
<math>\boldsymbol{s(t+1)=\delta(s(t),x(t));}</math>
Модель абстрактного автомата широко используется как базовая для построения дискретных моделей автоматов, распознающих, порождающих и преобразующих последовательности символов.
