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

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

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

${\displaystyle V=(A,B,Q,\varphi ,\psi )}$,

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

Абстрактный автомат с конечными множествами ${\displaystyle A,B,Q}$ называется конечным автоматом.^[3] Если же одно из этих множеств является бесконечным, то такой автомат называется бесконечным автоматом.^[4]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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

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

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

1. ↑ Кудрявцев, 1985, с. 5.
2. ↑ Кудрявцев, 1985, с. 6.
3. ↑ Кудрявцев, 1985, с. 14.
4. ↑ Кудрявцев, 1985, с. 29.
5. ↑ Кудрявцев, 1985, с. 18.

Эта страница в последний раз была отредактирована 11 февраля 2024 в 01:35.