Декомпозиция - автомат
Cтраница 1
Декомпозиция автоматов, в свою очередь, решает проблему кодирования внутренних состояний автомата и на структурном уровне приводит к синтезу оптимальных схем с точки зрения простоты комбинационной части автомата. [1]
Декомпозицией автомата А называется представление его в виде делителя каскадного соединения ( сплетения) других автоматов. [2]
Задача декомпозиции автомата состоит в представлении его частью автомата, построенного из более простых автоматов. Различные типы декомпозиции определяются, с одной стороны, связью компонент с исходным автоматом и, с другой - конструкциями, с помощью которых из данных элементов строятся более сложные автоматы. [3]
Примеры декомпозиции групповых и перестановочно-возвратных автоматов - частные случаи общей теоремы Крона-Роудза, утверждающей, что автоматы, полугруппы которых есть простые группы, а также тождественно-возвратный автомат с двумя состояниями неразложимы на более элементарные компоненты. Кроме того, любой автомат может быть разложен в последовательно-параллельное соединение тождественно-возвратных автоматов и ] автоматов простых групп, причем эти простые группы-гомоморфные образы всевозможных подгрупп полугруппы данного автомата. Для одного и того же автомата может существовать несколько разложений в последовательно-параллельное соединение автоматов простых групп и тождественно-возвратных автоматов с двумя состояниями. При этом может использоваться различное число автоматов простых групп и тождественно-возвратных компонент с двумя состояниями. [4]
Под декомпозицией автомата принято понимать построение для заданного автомата S сети С, состоящей из связанных между собой компонентных автоматов. [5]
Если А - произвольная каскадная декомпозиция автомата А и К - произвольный композиционный фактор группы перестановок подавтомата в А, то К является композиционным фактором группы перестановок подавтомата некоторой компоненты автомата А. [6]
Эта связь используется в декомпозиции автоматов. [8]
Отсюда следует, что нужно проводить декомпозицию автомата А на элементарные автоматы с минимальным числом связей между ними. Так как число связей зависит от числа запрещенных переходов в матрице соединений исходного автомата, то требуется таким образом изоморфно преобразовать матрицу соединений R автомата А, чтобы она содержала минимальное число запрещенных переходов. [9]
В этой главе строятся различные автоматные конструкции, рассматриваются декомпозиция автоматов ( доказывается теорема Крона - Роудза) и неразложимые групповые автоматы. [10]
Рассмотрим еще одну редукцию к автомату Мура, при которой декомпозиция автоматов с большим числом выходных сигналов и малым числом входных может оказаться более экономной. Леммы 7.12 - 7.14 являются аналогами соответствующих лемм для автоматов Мура. [11]
Если I 2, то переходим к 1 и проводим декомпозицию автомата А2 так, как это сделано с автоматом А. [12]
В главе 4 излагается доказательство Зейгера теоремы Крона - Роудза о декомпозиции автомата. Оно основывается на аппарате теории покрытий. Возможно, это доказательство будет ближе читателям, знакомым с работами Хартманиса и Стирнза по декомпозиции автоматов. [13]
Все перечисленные случаи декомпозиции абстрактных автоматов представляют собой так называемые чистые случаи декомпозиции автоматов. Таких автоматов, которые раскладываются только в параллельную или в последовательную или даже в смешанную работу автоматов, незначительное число по сравнению с множеством автоматов, которые не представимы параллельной, последовательной или смешанной декомпозицией. В связи с этим вводится понятие общей декомпозиции абстрактного автомата, которая понимается как представление абстрактного автомата совместной работой элементарных абстрактных автоматов со связями между ними. Общая декомпозиция соответствует разложению абстрактного автомата в композицию двух или большего числа абстрактных автоматов. Заметим, что в качестве элементарных абстрактных автоматов могут быть выбраны абстрактные автоматы с любым числом состояний, а параллельную, последовательную и смешанную декомпозиции абстрактных автоматов можно рассматривать как частные случаи общей декомпозиции автоматов. [14]
Поскольку в автомате Мура операция выражается через операцию о и определяющее отображение, декомпозиция автоматов Мура сводится к декомпозиции автоматов типа вход - состояние. [15]
Страницы: 1 2 3