Cтраница 2
Кроме полугрупповых автоматов общего вида ( автоматов Мили) изучаются полугрупповые автоматы Мура, характеризующиеся тем, что в них операция сводится к операции о и некоторому определяющему отображению / i: А - В. Существуют различные критерии того, что произвольный автомат является автоматом Мура. Один из них интересен тем, что им выделяется класс полугрупп, являющихся полугруппами входов таких автоматов. Автоматы могут быть избыточны по входам, по выходам, по состояниям. С устранением этой избыточности связано построение трех видов универсальных автоматов. [16]
Ниже будет показано, что любой абстрактный автомат может быть построен из элементарных абстрактных автоматов, в качестве которых можно выбрать автоматы с любым числом состояний, используя две формальные операции - умножение автоматов и запреты переходов. С содержательной точки зрения это означает, что произвольный автомат может быть представлен совместной работой более простых автоматов с некоторым числом связей между ними, при помощи которых реализуются запреты переходов. Приводится алгоритм декомпозиции произвольного абстрактного автомата на элементарные абстрактные автоматы, который соответствует представлению произвольного автомата композицией элементарных абстрактных автоматов. Решается задача оптимальной декомпозиции, при которой число связей между элементарными автоматами, представляющими работу произвольного автомата, минимально. [17]
Прежде всего определено множество классов конгруэнтности на множество X, а следовательно, определена полугруппа для произвольного автомата. Эта полугруппа, обозначаемая SM, содержит единицу. [18]
Эта операция состоит в следующем. Рассматривается произвольный автомат А с т входными и с п выходными узлами. [19]
Как было показано в предыдущих параграфах, число автоматов, обладающих специальными видами матриц соединений такими, например, как правильная и регулярная клеточные матрицы, невелико по сравнению с общим числом-автоматов. Поэтому автоматы, предста-вимые параллельной или последовательной работой двух или более автоматов, составляют небольшое число всего множества автоматов. В связи с этим необходимо научиться представлять произвольные автоматы совместной работой более простых автоматов. Такое представление сводится, по сути дела, к разложению произволь - - ного автомата по операции композиции автоматов. [20]
Ниже будет показано, что любой абстрактный автомат может быть построен из элементарных абстрактных автоматов, в качестве которых можно выбрать автоматы с любым числом состояний, используя две формальные операции - умножение автоматов и запреты переходов. С содержательной точки зрения это означает, что произвольный автомат может быть представлен совместной работой более простых автоматов с некоторым числом связей между ними, при помощи которых реализуются запреты переходов. Приводится алгоритм декомпозиции произвольного абстрактного автомата на элементарные абстрактные автоматы, который соответствует представлению произвольного автомата композицией элементарных абстрактных автоматов. Решается задача оптимальной декомпозиции, при которой число связей между элементарными автоматами, представляющими работу произвольного автомата, минимально. [21]
Ниже будет показано, что любой абстрактный автомат может быть построен из элементарных абстрактных автоматов, в качестве которых можно выбрать автоматы с любым числом состояний, используя две формальные операции - умножение автоматов и запреты переходов. С содержательной точки зрения это означает, что произвольный автомат может быть представлен совместной работой более простых автоматов с некоторым числом связей между ними, при помощи которых реализуются запреты переходов. Приводится алгоритм декомпозиции произвольного абстрактного автомата на элементарные абстрактные автоматы, который соответствует представлению произвольного автомата композицией элементарных абстрактных автоматов. Решается задача оптимальной декомпозиции, при которой число связей между элементарными автоматами, представляющими работу произвольного автомата, минимально. [22]