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