Элементы теории конечных автоматов
  • Регистрация
1 1 1 1 1 1 1 1 1 1 Рейтинг 4.00 (1 Голос)

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

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

Задачу декомпозиции абстрактного автомата можно форму-лировать как задачу разложения автомата по алгебрагическим операциям. Поэтому важно изучение свойств формальных операций над абстрактными автоматами. Рассмотрим задание алгебрагических операций умножения, суммирования автоматов.

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

Рис. 7.11. Иллюстрация операции умножения

Рис. 7.12. Графы автоматов и

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

Пусть автоматы И заданы графами на рис. 7.12, причем оба они инициальные с начальными состояниями (для ) и (для ) или для автомата это состояние задается парой Если приходит сигнал То параллельная работа автомата приводит к состоянию (см. рис. 7.12) () с выходным сигналом (). Если проанализировать все комбинации выходов и состояний, то получим граф автомата на рис. 7.13.

Рис. 7.13. Граф автомата

Если теперь ввести алфавиты для полученного автомата , получим:

Теперь граф автомата принимает вид как на рис. 7.14.

Рис. 7.14. Модифицированный граф автомата

Вторая операция умножения Соответствует параллельной работе автоматов И с одним выходом (рис. 7.15).

Рис. 7.15. Иллюстрация операции умножения

Для примера воспользуемся графами автоматов И (рис. 7.12) и составим алфавит составного автомата:

Тогда, полагая, что автоматы И инициальные с начальными состояниями И , получим граф автомата (рис. 7.16).

Рис. 7.16. Граф автомата

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

Для рассматриваемой операции для автоматов И из рис. 7.12 можно получить граф переходов, представленный на рис. 7.17, где обозначения: Входной сигнал На автомате , а Выходной сигнал На автомате .

Рис. 7.17. Граф переходов автомата

Рассмотрим суперпозицию автоматов И . Эта операция, обозначаемая , соответствует последовательной работе автоматов И (рис. 7.18).

Рис. 7.18. Модель суперпозиции автоматов

Если автоматы И заданы графами переходов, как на рис 7.19, то для суперпозиции в которой каждый автомат является инициальным с состояниями И Соответственно, граф переходов по состояниям можно изобразить как на рис. 7.20, где Это выходы автомата

Рис. 7.19. Графы переходов для исходных автоматов И

Рис. 7.20. Граф переходов для суперпозиции автоматов

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

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

 

Декомпозиция абстрактных автоматов - 4.0 out of 5 based on 1 vote

Добавить комментарий


Защитный код
Обновить