Задача синтеза автоматов

По аналогии с задачей синтеза СФЭ можно поставить задачу синтеза для автоматов. Имеется неограниченный набор базисных автоматов . Требуется собрать автомат с наперед заданным функционированием. При этом задача синтеза сталкивается с определенными проблемами.

Допустим, что нужно присоединить выход автомата к входу автомата . Это возможно при условии , так как иначе второй автомат не поймет сигналы, поступающие с первого. Это приводит к запутанной ситуации, когда некоторые соединения невозможны.

Чтобы преодолеть это препятствие, вводится понятие структурного автомата, в котором все алфавиты (входной, выходной и внутренних состояний) кодируются двоичными словами.

Пусть – конечное множество из элементов, а – множество двоичных слов длины , где . Произвольное инъективное отображение будем называть кодированием множества двоичными словами.

Произведем кодирование алфавитов для произвольного автомата :

Обозначим закодированные вход, выход и состояние автомата в момент времени соответственно . Тогда закон функционирования представится в виде

(2)

Полученный после кодирования автомат называют структурным. Будем считать, что структурный автомат имеет двоичных входов, двоичных выходов, а внутреннее состояние автомата задается двоичным словом длины . На рис. 3 показан абстрактный автомат и соответствующий ему структурный автомат.

… …

Рис. 3

Переход к структурному автомату обеспечивает два важных для синтеза преимущества.

1°. Совместимость входов и выходов, так как через них передается двоичная информация. Мы не будем давать общее определение схемы из структурных автоматов – оно аналогично СФЭ.

2°. Запишем соотношения (2) в «координатах»:

(3)

Из (3) следует, что закон функционирования структурного автомата задается системой булевых функций.