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

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

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

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

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

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

Многие из перечисленных выше задач могут рассматриваться как массовые (алгоритмические) проблемы. Для конечных автоматов большинство из них имеет положительное решение. А. Т. Находит применение как в других областях математики, так и в решении практич. Задач. Напр., средствами А. Т. Доказывается разрешимость нек-рых формальных исчислений. Применение методов и понятий А. Т. К изучению формальных и естественных языков привело к возникновению раздела теории алгоритмов - математической лингвистике. Понятие автомата может служить модельным объектом в самых разнообразных задачах, благодаря чему возможно применение А. Т. В различных научных и прикладных исследованиях. Лит.:[1] Автоматы. Сб. Ст., пер. С англ., М., 1956. [2] Глушков В.

М., Синтез цифровых автоматов, М., 1962. [3] Трахтенброт Б. А., Барздинь Я. М., Конечные автоматы, М., 1970. В. Б. Кудрявцев, Ю. И. Янов.