Теория автоматов. Книга 2. Учебное пособие

6.1. Композиция автоматов
Структурный синтез автоматов осуществляется на базе структурной
теории автоматов, в которой в отличие от абстрактной теории производится учет большого числа свойств реально существующих цифровых
автоматов. Абстрактный автомат представляет собой математическую
модель проектируемого устройства. В структурном же автомате учитывается структура входных и выходах сигналов, а также внутренняя структура автомата на уровне так называемых структурных схем. В структурной теории автоматов принят отсчет автоматного времени, начиная
с 0 такта, т. е. t = 0, 1, 2, …
Главной задачей структурной теории автоматов является нахождение общих приемов построения структурных схем автомата на основе
композиции элементарных автоматов, принадлежащих к заранее заданному конечному числу типов. Рассмотрим, как представляется автомат в структурной теории автоматов. У абстрактного автомата один
входной и один выходной каналы. В структурной же теории как входные, так и выходные каналы автомата считаются состоящими из нескольких элементарных входных и соответственно элементарных выходных каналов. По этим каналам передаются элементарные сигналы.
Набор всех возможных для данного автомата элементарных сигналов
называется структурным алфавитом данного автомата. Каждый элементарный входной канал подсоединен к входному узлу автомата, а
каждый элементарный выходной канал к выходному узлу автомата.
Сформулируем определение общего способа композиции автома-
тов. Пусть {A₁, A₂, …, A_n}(n ? 0) конечное множество автоматов.
Необходимо произвести объединение этих автоматов в систему совместно работающих автоматов. Введем некоторое конечное множество
узлов, которые назовем внешними входными узлами, и некоторое конечное множество других узлов, которые назовем внешними выходными узлами. Входные и выходные узлы автоматов A₁, A₂, …, A_n будем
называть внутренними входными и выходными узлами.
Композиция автоматов состоит в том, что в полученной системе,
состоящей из заданных автоматов A₁, A₂, …, A_n и внешних узлов, производится отождествление некоторых узлов (как внешних, так и внутренних). У цифровых автоматов операции отождествления узлов соответствует соединение этих узлов проводниками.
После проведения отождествления узлов произвольная система автоматов превращается в так называемую схему или сеть автоматов.
Будем считать, что автоматы, входящие в схему, работают совместно,
если в каждый момент t автоматного времени (t = 0, 1, 2, …) на все
внешние входные узлы схемы подается какой-либо