Автоматов Теория

АВТОМАТОВ ТЕОРИЯ, раздел дискретной математики, изучающий математические модели преобразователей дискретной информации, называемых автоматами. Примерами таких преобразователей являются как реальные системы (вычислительные машины, технические автоматы, живые организмы), так и абстрактные системы (абстрактные вычислительные машины, аксиоматические теории). Автоматов теория возникла в середине 20 века в связи с изучением автоматов как математических моделей биологических систем и вычислительных машин. В дальнейшем проблематика автоматов теории существенно расширилась.

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

Автомат можно охарактеризовать как устройство, имеющее входной и выходной каналы и находящееся в каждый дискретный момент времени в одном из внутренних состояний. По входному каналу в такой момент поступают сигналы-воздействия. В те же моменты по выходному каналу устройство выдаёт сигналы-реакции. Состояния автомата, сигналы-воздействия и сигналы-реакции задаются буквами соответствующих алфавитов: алфавита состояний, а также алфавитов входных и выходных сигналов. Законы взаимодействия букв этих алфавитов задаются двумя функциями - функцией переходов и функцией выходов, отображающими пары (состояние - входная буква), в состояния и выходные буквы соответственно. Входной средой для автомата является множество слов во входном алфавите, а внутренней и выходной его средами являются множества слов в алфавите состояний и выходном алфавите. Автомат побуквенно перерабатывает слова из входной среды в слова двух других сред. Этот процесс называется поведением автомата. Свойства алфавитов и функций определяют различные типы автоматов. В случае, когда все алфавиты конечны, получают конечный автомат, в противном случае автомат называют бесконечным. Замена функций на отношения приводит к частичным и недетерминированным автоматам; использование случайных функций приводит к вероятностному автомату. При интерпретации входной среды термами или графами приходят к автоматам над термами и автоматам в лабиринтах.

Большинство задач автоматов теории являются общими для основных видов управляющих систем, к ним относятся задачи анализа и синтеза автоматов, задачи о полноте, минимизации, а также задачи, связанные с эквивалентными преобразованиями автоматов. Задача анализа состоит в том, чтобы по заданному автомату описать его поведение или по неполным данным об автомате и его функционированию установить те или иные его свойства. Задача синтеза состоит в построении автомата с заданным поведением, или функционированием. К этой задаче примыкают проблемы, связанные с оценкой сложности автоматов, обладающих заданным поведением, а также с построением оптимальных в определённом смысле автоматов. Задача о полноте состоит в том, чтобы выяснить, можно ли данное множество автоматов получить из меньшего множества с помощью некоторых операций над автоматами. Задача минимизации автоматов состоит в минимизации значений параметров автоматов (например, числа состояний), при которой получается автомат, эквивалентный в том или ином смысле исходному. Помимо задач, общих для основных видов управляющих систем, в автоматов теории рассматриваются специфические проблемы, характерные для автоматов. Так, в зависимости от условий задачи поведение автоматов удобно задавать на разных языках (регулярные выражения, канонические уравнения, язык логики предикатов и т.п.), в связи, с чем важными задачами являются выбор достаточно удобного адекватного языка и перевод с одного языка на другой. С задачами синтеза и эквивалентных преобразований связана задача минимизации числа состояний автомата. В связи с моделированием поведения автоматов одного класса автоматами другого класса возникают задачи минимизации моделирующих автоматов и оценки их сложности. Специальный раздел автоматов теории связан с так называемыми экспериментами с автоматами. Основная задача этого раздела состоит в том, чтобы получить определённые сведения о строении автомата путём наблюдения его реакции на те или иные внешние воздействия. При этом возникают задачи, связанные с классификацией экспериментов и с вопросами разрешимости задач определёнными видами экспериментов, а также с оценками длин минимальных экспериментов, достаточных для решения тех или иных задач. Понятие эксперимента с автоматами используется также в задачах контроля автоматов. Специальными разделами автоматов теории являются игры автоматов и поведение автоматов в случайной среде, в которых рассматриваются вопросы взаимодействия автоматов друг с другом и с определёнными внешними средами. Многие из перечисленных выше задач могут рассматриваться как массовые проблемы (смотри Алгоритмическая проблема). Для конечных автоматов большинство из них имеет положительное решение.

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

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