Математическая энциклопедия - автоматов теория

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

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

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

Лит.:[1] Автоматы. Сб. ст., пер. с англ., М., 1956; [2] Глушков В. М., Синтез цифровых автоматов, М., 1962; [3] Трахтенброт Б. А., Барздинь Я. М., Конечные автоматы, М., 1970. В. Б. Кудрявцев, Ю. И. Янов.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985