Полугрупповой автомат
Cтраница 1
Кроме полугрупповых автоматов общего вида ( автоматов Мили) изучаются полугрупповые автоматы Мура, характеризующиеся тем, что в них операция сводится к операции о и некоторому определяющему отображению / i: А - В. Существуют различные критерии того, что произвольный автомат является автоматом Мура. Один из них интересен тем, что им выделяется класс полугрупп, являющихся полугруппами входов таких автоматов. Автоматы могут быть избыточны по входам, по выходам, по состояниям. С устранением этой избыточности связано построение трех видов универсальных автоматов. [1]
Каскадное соединение полугрупповых автоматов, отвечающее указанной тройке ( Г, а, /), определяется так же, как и для абсолютно чистых автоматов. [2]
Для сплетения полугрупповых автоматов имеют место утверждения, аналогичные предложению 6.2 и следствию из него. [3]
Наряду с линейными полугрупповыми автоматами целесообразно рассматривать кольцевые автоматы. В случае линейных автоматов множество End ( Л, B) EndAxHom ( A, В) представляет собой кольцо. [4]
Определения автомата и полугруппового автомата были даны в предисловии. Автомат А называется конечным, если конечны его основные множества А, X, В. В ряде случаев приходится рассматривать автоматы, множества А, В которых наделены некоторой алгебраической структурой, например являются линейными пространствами. В отличие от полугруппового автомат ( А, X, В), у которого множество входов также не наделено алгебраической структурой, будем называть абсолютно чистым. [5]
Очевидно выполнение аксиом полугруппового автомата. Понятно, что гомоморфный образ циклического автомата также является циклическим, поэтому все фактор-автоматы автомата Atm ( T) являются циклическими. [6]
Мы рассматриваем в основном полугрупповые автоматы. Рассмотрим автомат А - ( А, X, В) с произвольным множеством X входных сигналов. Возьмем в А тройку множеств ( Z, X, Y): пусть этой тройкой нужно породить подавтомат в А. [7]
Для того чтобы каждый полугрупповой автомат с полугруппой входов Г был автоматом Мура, необходимо и достаточно, чтобы Г была полугруппой Мура. [8]
Если речь идет о полугрупповых автоматах, то требуется, чтобы отображение Р: В - В было согласовано с умножением в полугруппе, и для линейных автоматов предполагается еще, что отображения а: А - А и f: С - С являются линейными отображениями. [9]
В основном в книге рассматриваются полугрупповые автоматы, и если в тексте нет никаких оговорок, то под автоматом понимается полугрупповой автомат. [10]
Очевидно, что если все Аа - полугрупповые автоматы, то их декартово произведение также является полугрупповым автоматом. [11]
 |
Последовательно-параллельная декомпозиция перестановочно-возвратного автомата. [12] |
Для того чтобы начать декомпозицию, рассмотрим стандартный полугрупповой автомат с множеством состояний S. Выберем в полугруппе все элементы ct, определяющие стягивающие отображения переходов. Сформируем подмножества вида Sct, отбросив те из них, которые целиком содержатся в других. [13]
Кроме полугрупповых автоматов общего вида ( автоматов Мили) изучаются полугрупповые автоматы Мура, характеризующиеся тем, что в них операция сводится к операции о и некоторому определяющему отображению / i: А - В. Существуют различные критерии того, что произвольный автомат является автоматом Мура. Один из них интересен тем, что им выделяется класс полугрупп, являющихся полугруппами входов таких автоматов. Автоматы могут быть избыточны по входам, по выходам, по состояниям. С устранением этой избыточности связано построение трех видов универсальных автоматов. [14]
Тогда ( ЕЛ, ЕГ, v) есть гомоморфизм соответствующих полугрупповых автоматов по выходным сигналам. Единственность этого гомоморфизма проверяется непосредственно аналогично тому, как это делалось в предыдущих предложениях. [15]
Страницы: 1 2 3