Анализ поведения автоматов

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