10.2. ДЕКОМПОЗИЦИЯ АБСТРАКТНЫХ АВТОМАТОВ

Под деком позицией, и общем случае, понимается представление абстрактного автомата совокупностью нескольких, более простых автоматов, Декомпозиция обычно соответствует параллельной, последовательной или смешанной работе более простых автоматов. Поэтому можно рассматривать несколько видов декомпозиции: параллельную, последовательную и смешанную. Перечисленные случаи представляют собой так называемые «чистые» виды декомпозиции. Таких автоматов, которые раскладываются только в параллельную или в последовательную или даже в смешанную работу автоматов — незначительное число по сравнению с множеством автоматов, которые не представимы параллельной, последовательной или смешанной декомпозицией. В связи с этим вводится понятие общей декомпозиции абстрактного автомата, которая понимается как представление абстрактного автомата совместной работой более простых автоматов со связями между ними. Задачу декомпозиции абстрактного автомата можно сформулировать как задачу разложения автомата по алгебраическим операциям. Поэтому изучение свойств формальных операций над абстрактными автоматами имеет большое значение. В качестве операций обычно рассматриваются следующие: умножение, суммирование, суперпозиция и композиция.

Рассмотрим задание алгебраических операций умножения, суммировании, суперпозиции автоматов.

Операции умножения двух автоматов и содержательно соответствует параллельной одновременной работе автоматов и Последнее может быть проиллюстрировано рис. 10.8. Иными словами, подача на вход автомата являющегося произведением автоматов

Рис. 10.8

Рис. 10.9

Рис. 10.10

входного сигнала соответствует тому, что на входы автоматов и А а одновременно и независимо друг от друга подаются входные сигналы

Различают две модификации операции умножения. Первая, обозначаемая х, применяется к абстрактным автоматам с различными входными алфавитами. Вторая, обозначаемая применяется к абстрактным автоматам имеющим общий входной алфавит, и является частным случаем операции X. Рассмотрим отдельно две модификации операции умножения.

Смысл операции х над двумя автоматами легко уяснить, рассматривая ее на конкретном примере. Пусть автоматы заданы своими графами (рис. 10.9; 10,10). Для простоты положим, что оба автомата — инициальные с начальными состояниями (для автомата (для автомата Так как операция X соответствует параллельной одновременной работе двух автоматов с раздельными входами, то построение графа автомата можно описать следующим образом. Очевидно, каждое состояние автомата будет однозначно соответствовать упорядоченной паре состояний автоматов . В начальный момент времени автомат будет иметь состояние Если на автомат приходит входной сигнал а на автомат — входной сигнал то автомат в соответствии со своим графом, должен перейти в состояние выдавая при этом выхойной сигнал а автомат в состояние выдавая выходной сигнал Для автомата такой переход соответствует фрагменту графа на рис, 10.11. Осуществляя перебор всех возможных комбинаций пар входных сигналов автоматов получим все возможные переходы автомата Заметим, что выходной сигнал автомата формируется как упорядоченная пара выходных сигналов автоматов Окончательный

Рис. 10.11

Рис. 10.12

Рис. 10.13

Рис. 10.14

Рис. 10.15

Рис. 10.16.

вариант графа автомата представлен на рис. 10.12. Обозначив алфавит состояний автомата через входной алфавит через а выходной алфавит через и осуществив соответствующую подстановку, получим граф автомата Л, (рис. 10.13).

Вторая операция умножения абстрактный автоматов соответствует параллельной одновременной работе автоматов с общим входом. Пусть автоматы заданы своими графами (рис. 10.9; 10.10). Положим, что автоматы — инициальные с начальными состояниями соответственно. Понятие общего входа автоматов означает, что если на вход автомата поступает входной сигнал то точно такой же сигнал поступает и на вход автомата Построение графа переходов автомата можно описать следующим образом. Каждое состояние автомата будет однозначно соответствовать упорядоченной паре состояний автоматов . В начальный момент времени автомат будет находиться в состоянии Если на автомат поступпсг входной сигнал то поступает и на вход автомата Поэтому автомат перейдет в состояние выдавая выходной сигнал а автомат — в состояние выдавая выходной сигнал Для автомата такой переход, очевидно, опишется фрагментом графа на рис, 10.14. Осуществляя перебор всех возможных входных сигналов, получим все возможные переходы автомата Выходной сигнал томата как и в случае операции х, формируется как упорядоченная пара выходных сигналов автоматов Окончательный вариант графа автомата представлен на рис. 10.15. Обозначив алфавит состояний автомата через входной алфавит через имходной алфавит — и осуществив соответствующую подстановку, получим следующий граф автомата (рис. 10.16).

Определим операцию суммирования двух автоматов и Такая операция обозначается знаком и ее результат соответствует параллельной неодновременной работе автоматов Иными словами, если задан автомат то любое входное слово автомата образуется чередованием входных букв автоматов а любое его выходное слово — чередованием выходных букв автоматов Иначе, если в момент времени на вход автомата поступает букна входного алфавита автомата то на выходе автомата появляется буква выходного алфавита автомата а в момент времени на вход автомата обязательно должна поступить буква входного алфавита автомата с появлением на выходе автомата буквы им ход но алфавита автомата На уровне автоматов это соответствует тому, что в момент времени на вход автомата

поступает некоторая буква из его входного алфавита, а на вход автомата поступает пустая буква, в момент времени на вход автомата поступает буква его входного алфавита, а на вход автомата пустая входная буква и т. д. Для выходов автоматов и аналогично. Построение графа автомата являющегося суммой двух автоматов можно описать следующим образом. Очевидно, каждое состояние автомата будет однозначно соответствовать упорядоченной паре состояний автоматов Пусть в качестве автоматов и выбраны инициальные автоматы (рис. 10.9; 10.10). В начальный момент времени автомат должен находиться в состоянии где начальное состояние автомата и начальное состояние автомата Если на автомат поступает входной сигнал то автомат должен осуществить переход в состояние выдавая при этом выходной сигнал у. В соответствии с определением операции на автомат в этот момент времени никаких входных сигналов поступать не должно. Для различия входных и выходных сигналов автоматов условимся входной сигнал автомата обозначать а выходной сигнал как Тогда указанный переход автомата можно описать следующим фрагментом его графа (рис. 10.17). Осуществив перебор всех возможных входных сигналов автоматов и учитывая, что они работают поочередно, получим все возможные переходы автомата Окончательный вариант графа автомата представлен на рис. 10.18

Рассмотрим суперпозицию автоматов Операция суперпозиции обозначается знаком и соответствует последовательной работе автоматов в соответствии с рис. 10.19. Очевидно, каждое состояние автомата будет однозначно соответствовать упорядоченной паре состояний автоматов Это связано с тем, что очередной выходкой сигнал автомата появляется только после завершения следующего процесса: на вход автомата поступает входной сигнал по этому входному сигналу автомат осуществляет переход в некоторое состояние выдавая при этом выходной сигнал сигнал является входным для автомата по сигналу поступающему на вход

Рис. 10.17.

Рис. 10.18.

Рис. 10.19.

Рис. 10.20

Рис. 10.21

Рис. 10.22

Рис. 10.23

он осуществляет переход в некоторое состояние выдавая выходной сигнал сигнал является выходным сигналом автомата а его состояние в рассматриваемый момент времени описывается упорядоченной парой состояний автоматов и Да. Пусть в качестве автоматов выбраны инициальные автоматы с начальными состояниями и (рис. 10.20; 10.21). Построим автомат . В начальный момент времени автомат должен находиться в состоянии Если на автомат поступает входной сигнал то автомат должен осуществить переход в состояние выдавая выходной сигнал Сигнал является входным для автомата По нему автомат должен осуществить переход в состояние выдавая выходной сигнал который является выходным сигналом автомата Для автомата такой переход очевидно опишется фрагментом графа на рис. 10.22. Осуществляя перебор всех возможных входных сигналов автомата получим все возможные переходы автомата Окончательный вариант графа автомата представлен на рис. 10.23.

Рассмотрим в самых общих чертах декомпозицию абстрактного автомата по операциям: произведение типа X, произведение типа сумма и суперпозиция.

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