АВТОМАТОВ КОМПОЗИЦИИ

— операции, используемые для порождения одних автоматов из других. Часто композицией наз. и результаты таких операций, т. е. полученные автоматы. Указанные операции носят алгебр. характер и являются основой структурных построений в алгебраической теории автоматов. Наиболее часто рассматривают следующие А. к.

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

Прямое произведение. Эта операция, примененная к мн-ву автоматов дает автомат такой, что А является декартовым произведением , а X и Y — соответственно Ф-ции переходов и выходов задают i соотношения:

Скрещенное произведение. Двуместная операция, применяемая к автоматам без выходов. Из автоматов получают автомат . такой, что , где — однозначные ф-ции. Скрещенное произведение, в котором полупрямым произведением.

Обобщив операции прямого, скрещенного и полупрямого произведений, получают операцию произведения автоматов. Эта операция, примененная к мн-ву автоматов дает автомат такой, что а X и Y — некоторые заданные мн-ва. Ф-ции переходов и выходов задают с помощью двух заданных однозначных отображений следующим образом:

где

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

Используя все приведенные выше операции, можно из данного мн-ва автоматов порождать новые автоматы. Это представляет теор. интерес для автоматов теории и, в особенности, важно для ее практических применений. В частности, алгебр, методами исследовали полноты проблему в теории автоматов, а также различного рода автоматов декомпозиции. Лит.: Глушков В. М. Абстрактная теория автоматов. «Успехи математических наук», 1961, т. 16, в. 5. М. И. Кратко.