Cтраница 1
Многообразие автоматов называется специальным, если оно замкнуто относительно свободных объединений. [1]
Многообразием автоматов называется класс всех автоматов, удовлетворяющих некоторому набору тождеств. Такие многообразия иногда называют многообразиями с переменной полугрупой входных сигналов в отличие от многообразия Г - автоматов - класса Г - автоматов, удовлетворяющих заданному набору Г - тождеств. [2]
Если многообразие автоматов X порождается одним автоматом, то каждое групповое многообразие из соответствующей X тройки в гэ 02 D 03 порождается одной группой. Следующая теорема указывает, какими именно группами порождаются эти многообразия. [3]
Теорема 12.2. Многообразия автоматов находятся во взаимно однозначном соответствии с вполне характеристическими конгруэнциями свободного автомата. [4]
Как и в случае многообразий автоматов, квазимногообразия допускают определение, не связанное со свободными объектами. [5]
Тождество zl xz2 x задает многообразие автоматов, у которых результат на выходе не зависит от состояния автомата, а зависит только от входного сигнала. [6]
Можно проверить, что Х - многообразие автоматов, и если А, 0 ( / 1 2), то ( Х Хт) 0 Х Х, значит, указанное отображение есть гомоморфизм. Понятно, что этот гомоморфизм является эпиморфизмом. [7]
Тождества z xl-z x2 и z1 xz2 x задают многообразие автоматов, выходные сигналы которых не зависят ни от состояния автомата, ни от сигнала, поступившего на его вход. [8]
Тождество z xix2 z x2xl, xlf x2eF - F ( X), определяет многообразие автоматов с переменной Г, в которых внешнее действие любых двух входных элементов перестановочно. [9]
Пересечение р ( ра по всем А из в также есть вполне характеристическая конгруэнция - она дает все тождества данного класса в, В частности, каждому многообразию автоматов в отвечает вполне характеристическая конгруэнция р тождеств, выполняющихся на всех автоматах из в. С другой стороны, каждую вполне характеристическую конгруэнцию в AtmfZ, X, Y) можно рассматривать как набор тождеств, который определяет многообразие автоматов. Если рассматривать только вполне характеристические конгруэнции в AtmfZ, X, Y), то указанное соответствие между многообразиями автоматов и такими конгруэнциями оказывается взаимно однозначным. [10]
Нетрудно показать, что это соответствие взаимно однозначно. Таким образом, изучение многообразий автоматов сводится к изучению насыщенных многообразий автоматов и многообразий полугрупп. [11]
Наряду с многообразиями значительный интерес представляют квазимногообразия. В частности, наряду с многообразиями автоматов рассматриваются квазимногообразия автоматов. Такой важный класс автоматов, как класс автоматов Мура, является квазимногообразием автоматов. [12]
Нетрудно показать, что это соответствие взаимно однозначно. Таким образом, изучение многообразий автоматов сводится к изучению насыщенных многообразий автоматов и многообразий полугрупп. [13]
Пересечение р ( ра по всем А из в также есть вполне характеристическая конгруэнция - она дает все тождества данного класса в, В частности, каждому многообразию автоматов в отвечает вполне характеристическая конгруэнция р тождеств, выполняющихся на всех автоматах из в. С другой стороны, каждую вполне характеристическую конгруэнцию в AtmfZ, X, Y) можно рассматривать как набор тождеств, который определяет многообразие автоматов. Если рассматривать только вполне характеристические конгруэнции в AtmfZ, X, Y), то указанное соответствие между многообразиями автоматов и такими конгруэнциями оказывается взаимно однозначным. [14]
Совокупность всех тождеств конкретного автомата ( или класса автоматов) есть вполне характеристическая конгруэнция свободного автомата. Совокупность автоматов, удовлетворяющих заданному набору тождеств, называется многообразием автоматов. Тождества и многообразия автоматов и биавтоматов изучаются в гл. [15]