2.7. Разложение автоматов и расщепляемый автомат

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

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

Алгоритм 2.2. Дано S требуется найти

При помощи аргументов, аналогичных тем, которые были использованы для алгоритма 2.1, можно показать, что алгоритм 2.2 требует не более итераций пункта 2, где n — мощность множества состояний S автомата М, а r - мощность множества . Таблица 2.6 иллюстрирует применение этого алгоритма для автомата A3, изображенного на рис. 2.5 для

Таблица 2.6

Алгоритм 2.2 для A3 и

Автомат или подавтомат, который содержит два или большее число изолированных подавтоматов, будем называть разложимым. Ранее упоминалось, что если содержит единственное состояние составляет множество всех состояний, соединенных с посредством цепей ребер любой длины. Следовательно, если составляет неразложимый изолированный подавтомат автомата М. Если то можно заключить, что автомат М неразложим. Теперь можно описать метод получения максимального разложения автомата, т. е. метод разложения автомата на максимально возможное число изолированных подавтоматов.

Алгоритм 2.3. Определение максимального разложения заданного автомата М с множеством состояний

(1) Пусть . Полагаем Выбираем любое состояние из например и определяем Множество — множество состояний изолированного подавтомата автомата M. (3) (а) Если то полагаем, что содержит состояния множества S, не содержащиеся в Увеличиваем k на единицу и возвращаемся к (2). (б) Если то подавтоматы, определяемые множествами представляют максимальное разложение автомата M. В частности, если , то автомат M неразложим.

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

Два или большее число автоматов называются сравнимыми, если они имеют одинаковые входные алфавиты. Пусть — сравнимые автоматы, представляющие N различных систем, и пусть — автомат, который состоит из изолированных подавтоматов называется расщепляемым автоматом автоматов и обозначается так: При заданных таблицах переходов таблица переходов может быть построена следующим образом. (1) Переобозначим состояния автомата если необходимо, так, чтобы не было в одном и том же автомате или в двух различных автоматах двух состояний, обозначенных одинаково. (2) Запишем строки всех N таблиц последовательно в одну общую таблицу; эта таблица является таблицей переходов автомата . Если определены графами, то граф переходов является просто объединением всех отдельных графов, состояния которых могут быть перенумерованы в случае необходимости в соответствии с указанным выше правилом.

Понятно, что расщепляемый автомат и, следовательно, каждый автомат, содержащий ряд подавтоматов, определенных так же, как может рассматриваться как «система», которая есть автомат , или

Рис. 2.6. Автомат А 4.

Рис. 2.7. Автомат А 5.

Рис. 2.8. Автомат

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

В качестве примера рис. 2.6 и таблица 2.7 представляют автомат а рис. 2.7 и таблица -автомат Расщепляемый автомат, составленный из автоматов представлен на рис. 2.8 и в таблице 2.9.

Таблица 2.7

Автомат А 4

Таблица 2.8

Автомат А 5

Таблица 2.9

Автомат