Абстрактный автомат
Абстра́ктный автома́т — в дискретной математике математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. На вход этому устройству поступают символы одного алфавита, на выходе оно выдаёт символы (в общем случае) другого алфавита.Шаблон:Sfn
Формально абстрактный автомат определяется как пятёрка
- <math>V = (A, B, Q, \delta, \lambda)</math>,
где <math>Q</math> — множество состояний автомата, A, B — входной и выходной алфавиты соответственно, из которых формируются строки, считываемые и выдаваемые автоматом, <math>\delta : Q \times A \rightarrow Q</math> — функция переходов, <math>\lambda : Q \times A \rightarrow B</math> — функция выходов.Шаблон:Sfn
Абстрактный автомат с конечными множествами <math>A, B, Q</math> называется конечным автоматом.Шаблон:Sfn Если же одно из этих множеств является бесконечным, то такой автомат называется бесконечным автоматом.Шаблон:Sfn
Функционирование автомата состоит в том, что по заданной входной последовательности и из заданного начального состояния автомат однозначно выдаёт две последовательности: последовательность состояний автомата <math>q:\mathbb{N}\to Q</math> и последовательность выходных символов <math>b:\mathbb{N}\to B</math>. Номера элементов этих последовательностей интерпретируются как дискретные моменты времени и называются также тактами. Эти последовательности определяются рекурсивно при помощи следующих уравнений, называемых каноническими уравнениями автомата:
- <math>\begin{cases}q(0)=q_1 \\ q(t+1)=\varphi(q(t),a(t)) \\ b(t) = \psi(q(t),a(t))\end{cases}</math>
где <math>\varphi</math> — функция переходов, <math>\psi</math> — функция выходов.
<math>a:\mathbb{N}\to A</math> здесь последовательность входных символов, <math>q_1\in Q</math> — начальное состояние. Абстрактный автомат с выделенным начальным состоянием называется инициальным автоматом.Шаблон:Sfn Такой автомат обычно обозначается <math>V_{q_1}</math>.
Допускается также рассмотрение конечной последовательности входных символов <math>a(t)</math>; в таком случае длина выходной последовательности <math>b(t)</math> будет такая же, как и длина <math>a(t)</math>, а длина <math>q(t)</math> на <math>1</math> больше. Говорят, что инициальный автомат <math>V_{q_1}</math> задаёт функцию <math>f:A^*\cup A^\omega \to B^*\cup B^\omega</math>, если для входной последовательности <math>a</math> автомат выдаёт выходную последовательность <math>f(a)</math>. Множество функций, задаваемых всевозможными инициальными автоматами со входным алфавитом <math>A</math> и выходным алфавитом <math>B</math>, есть в точности множество детерминированных функций из <math>A</math> в <math>B</math>.
Автомат с выделенным множеством конечных состояний называется терминальным автоматом.
Для уточнения свойств абстрактных автоматов введена классификация.
Абстрактные автоматы образуют фундаментальный класс дискретных моделей как самостоятельная модель, и как основная компонента машин Тьюринга, автоматов с магазинной памятью, конечных автоматов и других преобразователей информации.
Модель абстрактного автомата широко используется как базовая для построения дискретных моделей автоматов, распознающих, порождающих и преобразующих последовательности символов.
Вариации и обобщения
Есть огромное количество вариаций и обобщений классического понятия абстрактного автомата, определённого вверху.
Частичный автомат получится, если в определении разрешить функциям <math>\varphi</math> и <math>\psi</math> быть частичными. В таком случае автоматы, у которых эти функции являются тотальными, называются тотальными.
Недетерминированный автомат получится, если в определении разрешить функциям <math>\varphi</math> и <math>\psi</math> быть многозначными. В таком случае автоматы, у которых эти функции являются однозначные, называются детерминированными. Для недетерминированных автоматов часто также разрешают так называемые ε-переходы: в область определения функции <math>\varphi</math> добавляют специальный символ пустой строки <math>\varepsilon</math>, которого нет в алфавите <math>A</math>. Для инициальных недетерминированных автоматов иногда вместо одного начального состояния рассматривают непустое множество начальных состояний.
Автомат Мура получится, если функции <math>\varphi</math> и <math>\psi</math> будут зависеть только от <math>Q</math> и не зависеть от <math>A</math>. В таком случае автоматы, у которых эти функции могут зависеть от обоих переменных, называются автоматами Мили.
Автомат-распознаватель получится, если из определения вообще убрать множество выходных символов и функцию выходов. Обычно автоматы распознаватели всегда рассматривают с выделенным множеством конечных состояний. В таком случае автоматы, которые содержат множество выходных символов и функцию выходов называются автоматами-преобразователями.
Вероятностный автомат получится, если областью значений функций <math>\varphi</math> и <math>\psi</math> полагать не сами <math>A</math> и <math>B</math>, а множество случайных величин на <math>A</math> и <math>B</math> из некоторого вероятностного пространства.
В самом общем смысле под понятием «абстрактный автомат» понимают любой автомат, которые не структурный. В этом смысле абстрактные автоматы представляют собой элементы схем структурных автоматов. Вне противопоставления абстрактный автомат — структурный автомат прилагательное «абстрактный» обычно опускается и говорят просто автомат.