Cтраница 3
Рассматриваются конструкции в заданной схеме и конструкции, меняющие схему. В ситуации меняющейся схемы применяется, в частности, идея сплетения баз данных. Эта идея применялась ранее в задаче декомпозиции автоматов, и для баз данных естественно рассматривать задачу декомпозиции, здесь также используются сплетения. [31]
Цель данной книги - рассмотрение именно этого последнего аспекта, а именно рассмотрение автомата в качестве алгебраической структуры. Эта алгебраическая структура оказывается достаточно интересной для исследования. Кроме того, алгебраическое строение автомата одновременно дает информацию о строении реальных автоматов. Свидетельством этого является применение алгебраических методов в вопросах декомпозиции автоматов; в первую очередь здесь следует отметить известную теорему Крона - Роудза о декомпозиции полугрупповых автоматов. [32]
Для уменьшения числа сомножителей объединим те из них, у которых в результате объединения суммарные размерности входных и выходных векторов не превысят разрядности обрабатывающей части МПС. Строим двоичную таблицу, каждому столбцу которой взаимно однозначно соответствует выходная переменная, участвующая в образовании вектора Y, строке - вектор входных переменных ранга, не превышающего числа, равного разрядности МПС, образующий частичный граф переходов, соответствующий какому-либо сомножителю. Элемент таблицы ( /, /) равен 1, если / - и строке соответствует вектор, образующий частичный граф переходов, соответствующий 7 - й выходной переменной, и равен 0 в противном случае. Каждому покрытию столбцов строками таблицы соответствует один из вариантов полной декомпозиции исходного автомата. Учитывая ограничения, налагаемые на число выходных переменных каждого сомножителя, необходимо рассматривать только те покрытия, у которых число столбцов, покрываемых одной строкой, не превосходит числа, равного разрядности МПС. [33]
Одной из важных проблем теории графов является проблема разложения сложных графов на более простые по различным операциям. Решение задачи разложения играет в теории графов такую же роль, какую в математической логике играет общая задача разложения булевых функций. Методы, применяемые для разложения графов, обобщаются на конечные автоматы ( см. гл. VIII), что приводит к решению так называемой проблемы декомпозиции автоматов. [34]
В этой и в последующих главах книги рассматриваются вопросы теории конечных автоматов. Основное внимание уделяется построению алгоритмов синтеза автоматов на абстрактном и структурном уровнях. На абстрактном уровне эти алгоритмы позволяют уменьшить общий объем памяти автомата, а на структурном уровне приводят к построению схемы автомата с минимальной комбинационной частью. Конечные автоматы задаются ориентированными графами со взвешенными ребрами, а алгоритмы синтеза автоматов удобно реализуются в ЦВМ. Подробно рассматриваются формальные операции над автоматами, которые на структурном уровне соответствуют различным способам соединения автоматов между собой. Излагается проблема декомпозиции автоматов и ее решение, основанное на разложении автоматов, которое приводит к синтезу оптимальных структурных схем автоматов. Поэтому язык графов, изложенный в предыдущих главах, является весьма удобным языком для решения задач теории автоматов. [35]
Главы I-IV посвящены методам теории графов, на которых основано решение задач логического проектирования автоматов. В них рассматриваются теоретико-множественные и алгебраические операции над ориентированными графами, определяются свойства операций и основные алгебраические структуры, которые они образуют по аналогии с известными структурами множеств. Решаются задачи разложения графов по алгебраическим и теоретико-множественным операциям. Доказываются теоремы о разложении графов по различным операциям, формулируются алгоритмы разложения, даются оценки числа разложимых графов, а также решается задача отыскания минимального дополнения неразложимых графов до разложимых. Главы V-IX посвящены изложению логического проектирования автоматов и вычислительных структур с помощью методов теории графов. Здесь излагается алгебра абстрактных автоматов, которая на абстрактном уровне описывает различные виды соединений автоматов при построении схем сложных автоматов, и проблема декомпозиции абстрактных автоматов, которая заключается в представлении сложного абстрактного автомата совместной работой более простых абстрактных автоматов. Решается задача общей декомпозиции, позволяющая любой абстрактный автомат представлять работой элементарных абстрактных автоматов с минимальным числом связей между ними, и задача декомпозиции автомата на заданные блоки, которая приводит к представлению автомата в виде однородной структуры заданных стандартных блоков, соединенных между собой последовательно, параллельно или произвольным образом. Описывается декомпозиционный метод синтеза автоматов, основанный на решении задачи общей декомпозиции автоматов, исключающий этап структурного синтеза и приводящий к единому сквозному синтезу автоматов, который решает задачи логического проектирования на абстрактном уровне. [36]