WikiSort.ru - Не сортированное

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

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

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

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

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

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

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.

Для улучшения этой статьи желательно: Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное.