Групповой автомат

Cтраница 1

Групповой автомат можно разложить в последовательно-параллельное соединение двух автоматов, когда группа содержит подгруппу. Основная задача - разложение функции переходов, так как функция выходов всегда может быть восстановлена при помощи отображения переходов и отображения выходов из всей группы в выходной алфавит. Идея доказательства заключается в параметризации элементов группы, а следовательно, и в параметризации состояний стандартной машины. Переходы состояний находятся тогда отдельно для каждого параметра в соответствующем автомате. [1]

Любой групповой автомат разлагается на автоматы простых групп, являющихся гомоморфными образами подгрупп первоначальной группы. Автоматы простых групп неразложимы. [2]

Рассмотрим стандартный групповой автомат, каждому элементу полугруппы которого соответствует одно состояние. [3]

Пусть даны групповой автомат ( А, Г) и ( р, ря) - такая конгруэнция этого автомата, что фактор-автомат ( А / р, Г / Н) тран-зитивен. [4]

Согласно предложению 3.2, групповой автомат является автоматом Мура. Такой нормальный делитель, отвечающий ядерной конгруэнции, обозначим через Z и также назовем ядром автомата. [5]

Переходы в пространстве состояний группового автомата представляют собой перестановки этого множества, образующие группу. [6]

Теорема 12.10 каждому многообразию групповых автоматов сопоставляет три вложенных друг в друга многообразия групп. Теорема 12.11 каждой такой тройке многообразий групп сопоставляет многообразие групповых автоматов. Следующее утверждение показывает, что это соответствие обладает определенными свойствами замкнутости. [7]

В этом пункте будут рассмотрены неразложимые групповые автоматы. [8]

Теорема 7.11. Для того чтобы точный конечный групповой автомат А - ( А, Г) был неразложим, необходимо и достаточно, чтобы он не имел нетривиальных конгруэнции. [9]

А; - либо триггеры, либо групповые автоматы, делящие автомат А. [10]

В последовательно-параллельном соединении групповые компоненты всегда соответствуют действию групповых автоматов, а стягивающие компоненты добавляются для получения стягивающего действия. При обратной связи групповое и стягивающее свойства отображения переходов не сохраняются, в действительности же может быть получено отображение переходов любого вида. Если суть последовательно-параллельной декомпозиции заключается в том, что она рассоединяет состояния различных автоматов, насколько это возможно, то обратная связь пересоединяет состояния. [11]

А, компоненты Af которой либо триггеры, либо групповые автоматы, делящие исходный автомат А. [12]

Последовательно-параллельная декомпозиция перестановочно-возвратного автомата. [13]

Следовательно, перестановочно-возвратный автомат может быть разложен в соединение группового автомата и набора параллельно соединенных тождественно-возвратных автоматов с двумя состояниями. [14]

Объединение результатов теоремы 7.11 и предложения 7.8 завершает описание неразложимых групповых автоматов. [15]

Страницы: 1 2 3