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

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

Файл:Абстрактный автомат.jpg

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

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

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

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

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

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

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

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

$\{\begin{array}{c}q(0)=q_1\\ q(t+1)=\phi (q(t),a(t))\\ b(t)=\psi (q(t),a(t))\end{array}$

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

$a:\mathbb{N}\to A$ здесь последовательность входных символов, $q_1\in Q$ — начальное состояние. Абстрактный автомат с выделенным начальным состоянием называется инициальным автоматом.Шаблон:Sfn Такой автомат обычно обозначается $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$.

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

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

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

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

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

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

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

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

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

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

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

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

Литература

• Шаблон:Книга

• Шаблон:Книга

• Шаблон:Книга