Доказательство. при = (О;) мощность г-множества равна единице и выражение (2.8) принимает вид

0{Oi) = G„ ,{ai). (2.9)

это означает, что о-достижимое множество является множеством всех состояний автомата М. достижимых из О; при подаче входной последовательности длины п - 1 или меньше.

если известно, что начальное состояние автомата М принадлежит непустому множеству которое составляет тупиковый или изолированный подавтомат, то М можно упростить путем исключения всех состояний, которые не принадлежат множеству Si, и всех дуг, начинающихся в этих состояниях. полученный автомат хотя и необязательно является адекватным представлением исходной системы во все моменты времени, но адекватен ей в смысле поведения в будущем. это вытекает из того, что исключенные состояния никогда не могут быть достигнуты из начального состояния, и, следовательно, они в данном случае излишни. например, если известно, что начальным состоянием автомата лз, изображенного на рис. 2.5. является состояние 1, то точный анализ поведения автомата лз в будущем может быть проведен, несмотря на- то. что состояния 2, 3, 5, 6, 8, 9 и начинающиеся в них дуги будут исключены из графа переходов.

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

пусть {Si) обозначает множество всех состояний автомата М, соединенных с состояниями = {о, о.....o,-j

посредством k или меньшего числа дуг, причем направление дуг несущественно. в частности, Hq{Si) = Si. множество H(Si) есть объединение s-состояний, расположенных в строках Oi, Oi.....Oi 51-подтаблицы таблицы переходов автомата М, и состояний основного столбца таблицы переходов, соответствующих строкам 55-подтаблицы, в которых есть какое-либо состояние из множества s. с другой стороны, j (Si) можно составить путем просмотра графа переходов автомата М. если задано я.д), /г>1, то kii) может быть определено из соотношения

H,{Si) = H,{H, i{Si)). (2.10)

) Дуга - направленное соединение, /й<Т/?о - ненаправленное соединение двух вершин графа. {Прим. перев.)

Если H,(SO = H, {Si), ТО Я,„(5г) = Я, 1(5) для всех неотрицательных целых и и, следовательно, соста-

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

Алгоритм 2.2. Дано S; требуется найти Я(5). (1) Пусть Hq{Si) = Si. Полагаем k=\. (2) Определяем Я,(5,.) = Я,(Я, ,(5,)). (3) (а) Если Я,(5,) # Я, , то увеличиваем k на единицу и возвращаемся к (2). (б) Если Я,(5,) = Я, ,(5г). то H,(Si) = H{Si).

При помощи аргументов, аналогичных тем, которые были использованы для алгоритма 2.1, можно показать, что алгоритм 2.2 требует не более п - г Таблица 2.6 итераций пункта 2, где п - мощ-Алгоритм 2.2 ность множества состояний S ав-

для ЛЗ и 5;= {1,4} томата М, а г - мощность множества Si. Таблица 2.6 иллюстрирует применение этого алгоритма для автомата ЛЗ, изображенного на рис. 2.5 для 5 = {1, 4), Я(1, 4)={1. 2, 4, 5, 7, 8}.

Автомат или подавтомат, который содержит два или большее число изолированных подавтоматов, будем называть разложимым. Ранее упоминалось, что если 5; содержит единственное состояние Oi, то Н (Oi) составляет множество всех состояний, соединенных с о посредством цепей ребер любой длины. Следовательно, если H{Oi)S, то Я(0;) составляет неразложимый изолированный подавтомат автомата М. Если Я (Oj) = S, то можно заключить, что автомат М неразложим. Теперь можно описать метод получения максимального разложения автомата, т. е. метод разложения автомата на максимально возможное число изолированных подавтоматов.

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

(1) Пусть Si = S. Полагаем k=l. (2) Выб{1раем любое состояние из S, например Oi, и определяем HOi. Множество Я(0; - множество состояний А-го изолированного подавтомата автомата М. (3) (а) Если Я(0;)и Яо.и • • .. . [j Н(Oi Ф S, то полагаем, что Si содержит состояния множества S, не содержащиеся в Я(ои Я(ои ... ия(0;.

Увеличиваем k на единицу и возвращаемся к (2). (б) Если Я(Оги Я(ои • • • и Я(о = 5, то подавтоматы, определяемые множествами Я(0;, Я(0;).....Я(0;, представляют максимальное разложение автомата М. В частности, если Я(о) = 5, то автомат М неразложим.

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

Два или большее число автоматов называются сравнимыми, если они имеют одинаковые входные алфавиты. Пусть Ж;, .....Жд, - сравнимые автоматы, представляющие N различных систем, и пусть Ж - автомат, который состоит из изолированных подавтоматов Ж;, М, Жд,. Ж называется расщепляемым автоматом автоматов

Ж;, Жз..... Жд, и обозначается так: АСЖ;, М, , Жд,).

При заданных таблицах переходов Ж;, Жз, • . ., Жy таблица переходов А (Ж,, Жз.....Жд,) может быть построена следующим образом. (1) Переобозначим состояния автомата Ж,-, если необходимо, так, чтобы не было в одном и том же автомате или в двух различных автоматах двух состояний, обозначенных одинаково. (2) Запишем строки всех N таблиц последовательно в одну общую таблицу; эта таблица является

таблицей переходов автомата А (Ж;, .....М). Если

Ж,- определены графами, то граф переходов А (Ж;, ..... Жд,)

является просто объединением всех отдельных графов, состояния которых могут быть перенумерованы в случае необходимости в соответствии с указанным выше правилом.

Понятно, что расщепляемый автомат А (Ж;, Жз.....Жy)

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

4 а. гилл