Декомпозиция абстрактных автоматов

Под декомпозицией понимается представление абстрактного автомата совокупностью нескольких более простых автоматов.

Задача декомпозиции абстрактного автомата – это задача разложения автомата по алгебраическим операциям. В качестве операций обычно рассматриваются такие: умножение, суммирование, суперпозиция и композиция.

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

Операция умножения двух автоматов А₁ и А₂ содержательно соответствует параллельной одновременной работе автоматов А₁ и А₂, т.е. подача на вход автомата А₃ входного сигнала соответствует тому, что на входы автоматов А₁ и А₂ одновременно и независимо друг от друга подаются входные сигналы и .

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

Пример: Пусть автоматы А₁ и А₂ заданы графами.

Так как операция соответствует одновременной параллельной работе двух А₁ и А₂ с раздельными входами, то построение графа А₃ можно описать таким образом: каждое состояние автомата А₃ будет однозначно соответствовать упорядоченной паре состояний автоматов А₁ и А₂. В начальный момент времени А₃ будет иметь состояние . Осуществляя перебор всех возможных комбинаций пар входных сигналов автоматов А₁ и А₂, получаем все возможные переходы автомата А₃.

Операция суммирования + двух автоматов А₁ и А₂ соответствует параллельной неодновременной работе автоматов А₁ и А₂; т.е. если задан автомат А₃=А₁+А₂, то любое входное слово автомата А₃ образуется чередованием входных букв А₁ и А₂, а любое выходное слово – чередованием выходных букв А₁ и А₂.

Операция суперпозиции соответствует последовательной работе автоматов А₁ и А₂

Построим автомат А₃=А₁*А₂

Глава 10

Структурная теория автоматов

Композиция автоматов

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

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

Структурная теория автоматов и абстрактная теория автоматов являются двумя различными частями общей теории автоматов. При синтезе реальных автоматов многие вопросы проще и эффективнее решаются на уровне абстрактной теории. К числу таких вопросов относится определение необходимого объема памятиавтомата (т.е. числа его состояний), переходов в памяти, а также вопросы, относящиеся к минимизации числа состояний автомата. В то же время имеется ряд вопросов – таких, например, как вопрос о композиции автоматов, - сама постановка которых выводит за рамки абстрактной теории автоматов.

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

Каждый элементарный канал (входной или выходной) подсоединяется к так называемому узлу. Существуют входные узлы автомата и выходные узлы автомата. В каждом автомате осуществляется определенная циркуляция элементарных сигналов. Элементарные входные сигналы поступают сначала на входные узлы, а затем по подсоединенным к ним элементарным входным каналам передаются внутрь автомата. Элементарные выходные сигналы, выходя из автомата по элементарным выходным каналам, поступают на соответствующие выходные узлы.

Сформулируем определение общегоспособакомпозицииавтоматов.

Пусть (где ) конечное множество автоматов. Произведем объединение этих автоматов в систему совместно работающих автоматов следующим образом.

Введем в рассмотрение некоторое конечное множество узлов, которое назовем внешнимивходнымиузлами, и некоторое конечное множество других узлов, которое назовем внешнимивыходнымиузлами (полюсами). Эти узлы предполагаются отличными от входных и выходных узлов рассматриваемых автоматов, которые будем называть внутренними (входными и выходными) узлами.

Композиция автоматов состоит в том, что в полученной системе, состоящей из данных автоматов и внешних узлов, производится отождествлениенекоторыхузлов (как внешних, так и внутренних). С точки зрения совместной работы системы автоматов смысл операции отождествления узлов состоит в том, что элементарный сигнал, попадающий на один из узлов, входящих во множество отождествленных между собой узлов, попадает сразу на все узлы этого множества. Для электронных ЦА операции отождествления узлов соответствует соединение этих узлов проводниками.

В результате проведения операции отождествления (соединения) узлов, все узлы, входящие в данную систему (внутренние и внешние), разобьются на попарно непересекающиеся множества отождествленных между собой узлов.

После проведенных отождествлений система автоматов превращается в так называемую схему (сеть) автоматов. Будем считать, что автоматы, входящие в схему, работают совместно, если в каждый момент автоматного времени ( ) на все внешние входные узлы схемы подается какой-либо набор элементарных сигналов (структурный входной сигнал схемы), а с внешних выходных узлов схемы снимается получающийся на них набор элементарных выходных сигналов (структурный выходной сигнал).

Предположим, что в каждый момент дискретного времени структурный выходной сигнал схемы однозначно определяется 1) поступившей к этому времени последовательностью структурных входных сигналов; 2) начальными состояниями входящих в схему автоматов и 3) сделанными при построении схемы отождествлениями узлов. Построенная схема может рассматриваться как некоторый ЦА , а сама схема называться структурнойсхемой этого автомата.

Полученный описанным способом автомат есть результат композиции исходных автоматов .

Однако не всякое отождествление узлов приводит к схеме, которую можно рассматривать как структурную схему некоторого автомата. Необходимо соблюдать два условия корректности схемы:

- в любой момент времени на каждый узел схемы (как внешний, так и внутренний) поступает какой-либо элементарный сигнал;

- неоднозначность элементарных сигналов в каком-нибудь узле схемы хотя бы в один момент времени является недопустимой (существуют два источника неоднозначности элементарного сигнала в узле 1) если к какому-то узлу подсоединено одновременно несколько выходных узлов, являющихся источниками элементарных сигналов; 2) наличие петли или циклической цепи в структурной схеме).

Правильнойкомпозициейавтоматов называется операция построения схемы автомата, для которой выполняются три условия:

1. Для любого узла схемы должна существовать цепь, состоящая из некоторого множества (м.б. пустого) автоматов Мили, начинающаяся каким-нибудь задающим (внешние входные или внутренние выходные узлы автомата Мура) узлом и кончающаяся узлом (условие передачи элементарных сигналов от задающих узлов на все узлы автомата в каждый момент автоматного времени).

2. Любой узел схемы должен быть отождествлен (соединен) не более чем с одним внешним входным или внутренним выходным узлом.

3. Любая нетривиальная (содержащая не менее одного ЦА) петля в схеме должна содержать в своем составе хотя бы один автомат Мура.

Глава 11