Cтраница 3
Следует заметить, что указанный порядок сомножителей существен. Такое представление гомоморфизма автомата называется каноническим разложением гомоморфизма. Доказательство проведено для случая гомоморфизма полугруппового автомата. [31]
Из определения и2 и равенств (7.2) следует, что / х2 - гомоморфизм полугрупп. Очевидно, что иг есть гомоморфизм V на всю полугруппу S. Проверим справедливость условия (1.1) из определения гомоморфизма полугрупповых автоматов. [32]
Определения автомата и полугруппового автомата были даны в предисловии. Автомат А называется конечным, если конечны его основные множества А, X, В. В ряде случаев приходится рассматривать автоматы, множества А, В которых наделены некоторой алгебраической структурой, например являются линейными пространствами. В отличие от полугруппового автомат ( А, X, В), у которого множество входов также не наделено алгебраической структурой, будем называть абсолютно чистым. [33]
Цель данной книги - рассмотрение именно этого последнего аспекта, а именно рассмотрение автомата в качестве алгебраической структуры. Эта алгебраическая структура оказывается достаточно интересной для исследования. Кроме того, алгебраическое строение автомата одновременно дает информацию о строении реальных автоматов. Свидетельством этого является применение алгебраических методов в вопросах декомпозиции автоматов; в первую очередь здесь следует отметить известную теорему Крона - Роудза о декомпозиции полугрупповых автоматов. [34]
В качестве дальнейшего обобщения можно рассматривать автоматы, у которых множества состояний и выходов заменяются объектами произвольной категории К. Для фиксированной пары объектов А, В из К рассмотрим множество EodfA, B) EndAx Hom ( A, В), где End ( A) - множество всех морфизмов из А в А, а Нот ( А, В) - множество всех морфизмов из А в В. Pi ( P2 Ф г) - Относительно этого умножения EndfA, В) - полугруппа. Автомат над К определяется как тройка ( А, X, В), в которой А, В - объекты из К, я. Если А - Г - полугруппа и отображение / / Г - ЕпА ( А, В) есть гомоморфизм полугрупп, то ( А, Г, В) - полугрупповой автомат в категории К. [35]
Прежде всего определено множество классов конгруэнтности на множество X, а следовательно, определена полугруппа для произвольного автомата. Эта полугруппа, обозначаемая SM, содержит единицу. Действие автоматов окажется одинаковым только тогда, когда они начинают работать из соответствующих начальных состояний. Полугрупповой автомат должен начинать работать из единичного состояния, а первоначальный автомат - из некоторого выбранного состояния. Функция выходов строится следующим образом: из каждого класса конгруэнтности выбирается произвольная входная последовательность, соответствующее ей состояние находится в первоначальном автомате при выбранном заранее начальном состоянии, для построенного состояния находится в первоначальном автомате выходной элемент. [36]
При этом Al - ( A Xt) есть полугрупповой полуавтомат, А2 ( А, Хг, В) - произвольный - автомат. Мы должны будем предполагать, что полугруппа Xt действует на множестве Х2 слева: Х2 есть левый Xt-полигон. Например, такая ситуация имеет место, если Х1 - подполугруппа из SA, а A 2 - подмножество из Funf А. В), замкнутое относительно естественного действия ( умножения) слева элементов из А. В этом случае тройка ( X, a, / JJ, в которой X - полугруппа, or - гомоморфизм из X в AY. Значит, А ( Х, а, р) является полугрупповым автоматом. Доя фиксированных At и А2 класс полугрупповых соединений составляет категорию с морфизмами - гомоморфизмами полугрупповых автоматов. Построим универсальный притягивающий объект этой категории. Относительно этого умножения X является полугруппой. Как и ранее, обозначим через п1 п2 проектирования множества X на XL, X2 соответственно. [37]
При этом Al - ( A Xt) есть полугрупповой полуавтомат, А2 ( А, Хг, В) - произвольный - автомат. Мы должны будем предполагать, что полугруппа Xt действует на множестве Х2 слева: Х2 есть левый Xt-полигон. Например, такая ситуация имеет место, если Х1 - подполугруппа из SA, а A 2 - подмножество из Funf А. В), замкнутое относительно естественного действия ( умножения) слева элементов из А. В этом случае тройка ( X, a, / JJ, в которой X - полугруппа, or - гомоморфизм из X в AY. Значит, А ( Х, а, р) является полугрупповым автоматом. Доя фиксированных At и А2 класс полугрупповых соединений составляет категорию с морфизмами - гомоморфизмами полугрупповых автоматов. Построим универсальный притягивающий объект этой категории. Относительно этого умножения X является полугруппой. Как и ранее, обозначим через п1 п2 проектирования множества X на XL, X2 соответственно. [38]