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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

,

где  — множество состояний автомата, A, B — входной и выходной алфавиты соответственно, из которых формируются строки, считываемые и выдаваемые автоматом,  — функция переходов,  — функция выходов.[2]

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

Абстрактный автомат с конечными множествами называется конечным автоматом.[3] Если же одно из этих множеств является бесконечным, то такой автомат называется бесконечным автоматом.[4]

Функционирование автомата состоит в том, что по заданной входной последовательности и из заданного начального состояния автомат однозначно выдаёт две последовательности: последовательность состояний автомата и последовательность выходных символов . Номера элементов этих последовательностей интерпретируются как дискретные моменты времени и называются также тактами. Эти последовательности определяются рекурсивно при помощи следующих уравнений, называемых каноническими уравнениями автомата:

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

здесь последовательность входных символов, — начальное состояние. Абстрактный автомат с выделенным начальным состоянием называется инициальным автоматом.[5] Такой автомат обычно обозначается .

Допускается также рассмотрение конечной последовательности входных символов ; в таком случае длина выходной последовательности будет такая же, как и длина , а длина на больше. Говорят, что инициальный автомат задаёт функцию , если для входной последовательности автомат выдаёт выходную последовательность . Множество функций, задаваемых всевозможными инициальными автоматами со входным алфавитом и выходным алфавитом , есть в точности множество детерминированных функций из в .

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

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

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

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

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

[править | править код]

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

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

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

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

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

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

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

Литература

[править | править код]
  • Виктор Михайлович Глушков. Абстрактная теория автоматов. — Успехи математических наук, т. XVI, вып. 5 (101). — М., 1961. — С. 476.
  • В. Б. Кудрявцев, С. В. Алёшин, А. С. Подколзин. Введение в теорию автоматов. — М.: Наука, 1985. — С. 320.
  1. Кудрявцев, 1985, с. 5.
  2. Кудрявцев, 1985, с. 6.
  3. Кудрявцев, 1985, с. 14.
  4. Кудрявцев, 1985, с. 29.
  5. Кудрявцев, 1985, с. 18.