Автоматов композиции

операции, позволяющие из одних автоматов получать другие, более сложные, путем соединения исходных автоматов по определенным правилам. А. к. играют важную роль в задачах синтеза и разложения автоматов. Важнейшими и наиболее употребительными А. к. являются прямое произведение, суперпозиция, обратная связь. Прямым произведением автоматов [img: http://localhost:8080/file/010106-114.jpg] [img: http://localhost:8080/file/010106-115.jpg] наз. автомат [img: http://localhost:8080/file/010106-116.jpg] = [img: http://localhost:8080/file/010106-117.jpg] у к-рого [img: http://localhost:8080/file/010106-118.jpg] а функции [img: http://localhost:8080/file/010106-119.jpg] определяются соотношениями: [img: http://localhost:8080/file/010106-120.jpg] В вопросах полноты и синтеза автоматов большую роль играет операция обратной связи. Эта операция применима к автоматам с пвходами и твыходами: [img: http://localhost:8080/file/010106-121.jpg] [img: http://localhost:8080/file/010106-122.jpg] [img: http://localhost:8080/file/010106-123.jpg] таким, что для нек-рых [img: http://localhost:8080/file/010106-124.jpg] имеет место [img: http://localhost:8080/file/010106-125.jpg] и функция [img: http://localhost:8080/file/010106-126.jpg] не зависит от [img: http://localhost:8080/file/010106-127.jpg] т. е. [img: http://localhost:8080/file/010106-128.jpg] Тогда в применении к i-му выходу и j-му входу автомата [img: http://localhost:8080/file/010106-129.jpg] операция обратной связи дает автомат [img: http://localhost:8080/file/010106-130.jpg] [img: http://localhost:8080/file/010106-131.jpg] такой, что [img: http://localhost:8080/file/010106-133.jpg] [img: http://localhost:8080/file/010106-132.jpg] Кроме указанных, иногда используются другие виды А. к., напр, произведение, прямая сумма, полупрямое произведение и т. д.