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

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