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

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

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

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

$V=(A,B,Q,\delta ,\lambda )$,

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

Функциональная схема абстрактного автомата

Абстрактный автомат с конечными множествами $A,B,Q$ называется конечным автоматом. Если же одно из этих множеств является бесконечным, то такой автомат называется бесконечным автоматом.

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

${\begin{cases}q(0)=q_{1}\\q(t+1)=\varphi (q(t),a(t))\\b(t)=\psi (q(t),a(t))\end{cases}}$

где \phi – функция переходов, \psi – функция выходов.

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

Допускается также рассмотрение конечной последовательности входных символов $a(t)$; в таком случае длина выходной последовательности $b(t)$ будет такая же, как и длина $a(t)$, а длина $q(t)$ на $1$ больше. Говорят, что инициальный автомат $V_{q_{1}}$ задаёт функцию $f:A^{*}\cup A^{\omega }\to B^{*}\cup B^{\omega }$, если для входной последовательности $a$ автомат выдаёт выходную последовательность $f(a)$. Множество функций, задаваемых всевозможными инициальными автоматами со входным алфавитом $A$ и выходным алфавитом $B$, есть в точности множество детерминированных функций из $A$ в $B$.

Автомат с выделенным множеством конечных состояний называется терминальным автоматом.

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

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

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

Вариации и обобщения

Есть огромное количество вариаций и обобщений классического понятия абстрактного автомата, определённого вверху.

Частичный автомат получится, если в определении разрешить функциям $\varphi$ и $\psi$ быть частичными. В таком случае автоматы, у которых эти функции являются тотальными, называются тотальными.

Недетерминированный автомат получится, если в определении разрешить функциям $\varphi$ и $\psi$ быть многозначными. В таком случае автоматы, у которых эти функции являются однозначные, называются детерминированными. Для недетерминированных автоматов часто также разрешают так называемые ε-переходы: в область определения функции $\varphi$ добавляют специальный символ пустой строки $\varepsilon$, которого нет в алфавите $A$. Для инициальных недетерминированных автоматов иногда вместо одного начального состояния рассматривают непустое множество начальных состояний.

Автомат Мура получится, если функции $\varphi$ и $\psi$ будут зависеть только от $Q$ и не зависеть от $A$. В таком случае автоматы, у которых эти функции могут зависеть от обоих переменных, называются автоматами Мили.

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

Вероятностный автомат получится, если областью значений функций $\varphi$ и $\psi$ полагать не сами $A$ и $B$, а множество случайных величин на $A$ и $B$ из некоторого вероятностного пространства.

В самом общем смысле под понятием «абстрактный автомат» понимают любой автомат, которые не структурный. В этом смысле абстрактные автоматы представляют собой элементы схем структурных автоматов. Вне противопоставления абстрактный автомат — структурный автомат прилагательное «абстрактный» обычно опускается и говорят просто автомат.

Литература

• Виктор Михайлович Глушков. Абстрактная теория автоматов. — Успехи математических наук, т. XVI, вып. 5 (101). — М., 1961. — С. 476.

• Виктор Михайлович Глушков. Синтез цифровых автоматов. — М.: Государственное издательство физико-математической литературы, 1962. — С. 476.

• В. Б. Кудрявцев, С. В. Алёшин, А. С. Подколзин. Введение в теорию автоматов. — М.: Наука, 1985. — С. 320.