imported>Moon979: оформление - добавлены пропущенные теги $для макросов \phi и \psi. \phi преобразован в \varphi для согласованности с остальным текстом$

2025-09-16T14:03:12Z

оформление - добавлены пропущенные теги <math> для макросов \phi и \psi. \phi преобразован в \varphi для согласованности с остальным текстом

Новая страница

'''Абстра́ктный автома́т''' — [[дискретная математика|в дискретной математике]] [[математическая абстракция]], [[модель]] [[дискретное устройство|дискретного устройства]], имеющего один вход, один выход и в каждый момент времени находящегося в одном [[состояние|состоянии]] из множества возможных. На вход этому устройству поступают [[символ]]ы одного [[Алфавит (информатика)|алфавита]], на выходе оно выдаёт символы (в общем случае) другого алфавита.{{sfn|Кудрявцев|1985|с=5}} [[Файл:Абстрактный автомат.jpg|220px|thumb|right|Абстрактный автомат]]

Формально абстрактный автомат определяется как пятёрка
:<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|Кудрявцев|1985|с=6}}
[[Файл:Функциональная схема абстрактного автомата.jpg|440px|thumb|left|Функциональная схема абстрактного автомата]]

Абстрактный автомат с конечными множествами <math>A, B, Q</math> называется [[Конечный автомат|конечным автоматом]].{{sfn|Кудрявцев|1985|с=14}} Если же одно из этих множеств является бесконечным, то такой автомат называется бесконечным автоматом.{{sfn|Кудрявцев|1985|с=29}}

Функционирование автомата состоит в том, что по заданной входной последовательности и из заданного начального состояния автомат однозначно выдаёт две последовательности: последовательность состояний автомата <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|Кудрявцев|1985|с=18}} Такой автомат обычно обозначается <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> из некоторого [[Вероятностное пространство|вероятностного пространства]].

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

== Литература ==
* {{книга
|заглавие = Абстрактная теория автоматов
|автор = [[Виктор Михайлович Глушков]]
|isbn =
|страницы = 476
|год = 1961
|издание = [[Успехи математических наук]], т. XVI, вып. 5 (101)
|место = М.
|издательство =
}}

* {{книга
|заглавие = Синтез цифровых автоматов
|автор = [[Виктор Михайлович Глушков]]
|isbn =
|страницы = 476
|год = 1962
|издание =
|место = М.
|издательство = [[Государственное издательство физико-математической литературы]]
}}

* {{книга
|заглавие = Введение в теорию автоматов
|автор = В. Б. Кудрявцев, С. В. Алёшин, А. С. Подколзин
|isbn =
|страницы = 320
|год = 1985
|издание =
|место = М.
|издательство = [[Наука (издательство)|Наука]]
|ref = Кудрявцев
}}

{{вс}}
{{Нет источников |дата=2012-10-12}}

[[Категория:Теория автоматов]]

Абстрактный автомат - История изменений

imported>Moon979: оформление - добавлены пропущенные теги для макросов \phi и \psi. \phi преобразован в \varphi для согласованности с остальным текстом

imported>Moon979: оформление - добавлены пропущенные теги $для макросов \phi и \psi. \phi преобразован в \varphi для согласованности с остальным текстом$