Спирина, М.С. Дискретная математика

В рамках обшей задачи синтеза конечных автоматов возникают отдельные частные проблемы. Проблема существования', существует ли автомат данного типа, соответствующий заданным условиям? Проблема единственности : единственным ли образом можно синтезировать заданный автомат? Проблема минимизации', по заданным начальным условиям с помощью эквивалентных преобразований привести автомат к изо­ морфному, удовлетворяющему определенным критериям опти­ мальности. При выборе языка предпочтение отдается языкам, основан­ ным на использовании логики предикатов. Обратная задача — задача анализа — заключается в поиске по заданному графу конечного автомата Z отображения слов входно­ го алфавита X во множество слов его выходного алфавита Y. Для конечных детерминированных автоматов разработано до­ статочное число алгоритмов их синтеза и анализа. Анализ можно рассматривать как вычисление предиката. Так как каждый предикат полностью характеризуется своим множе­ ством истинности, то задача анализа автоматов может быть сведе­ на к поиску множества истинности соответствующего предиката. В таком случае говорят, что это множество распознается автома­ том. Причем для многих классов автоматов классы распознавае­ мых ими множеств хорошо известны. Однако далеко не всегда по заданным автомату и множеству удается установить, насколько точно автомат распознал это мно­ жество. Так, не существует алгоритмов, которые смогли бы вы­ полнить эту задачу, она считается алгоритмически неразрешимой. Решение задач анализа и синтеза автоматов связано с поняти­ ем автоматного времени. Так, в синхронных автоматах моменты времени, в которые фиксируются изменения их состояний, зада­ ют специальные устройства — генераторы синхросигналов. Они выдают импульсы через равные промежутки времени, задавая так называемый постоянный интервал дискретности. Задача декомпозиции заключается в поиске таких эквивалент­ ных преобразований автомата, которые при минимальном числе состояний имеют те же свойства, что и при заданном. То есть необходимо определить, как можно получить заданный автомат Z, соединив минимальное число более простых автоматов, может быть, за счет усложнения комбинационных схем. Но при этом поведение автомата характеризуется одинаковыми внешними про­ явлениями. Так как понятие композиции имеет разное значение, то задачу декомпозиции автоматов можно ставить по-разному. Простейшим примером является рассмотрение автоматов в виде суммы, произведения или последовательного соединения. Но наи­ больший интерес представляют композиции более простые, чем 352