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


 

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

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

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

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

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

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

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

 
 

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

 
 

Для автоматов А1 и А2, приведенных выше, операция + будет представлена следующим образом:

 
 

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

Построим автомат А312

Глава 10

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



Дата добавления: 2016-07-18; просмотров: 1618;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.006 сек.