7.4. Определение минимальных форм

Множество Sj, входящее в правильную группировку Sj, .....S„, будем называть совместимым множеством.

Лемма 7.1. Каждая пара состояний в совместимом множестве должна быть совместимой.

Доказательство. Рассмотрим состояния и из множества S] правильной группировки Sj, Sj- •••• п- По теореме 7.1 существует автомат Ж, в котором одно состояние, обозначенное о, квазиэквивалентно о и a. Тогда реакции

автомата, находящегося в состояниях или , на любую

входную последовательность , допустимую для обоих состояний, должны быть одинаковыми, так как каждая из этих реакций должна быть такой же, как реакция автомата Жа на входную последовательность . Следовательно, по определению и должны быть совместимы.

В дальнейшем С-множеством автомата Ж будем называть множество состояний автомата Ж, которое удовлетворяет двум следующим условиям: (1) каждая пара состояний из С-множества совместима; (2) это множество не является подмножеством другого С-множества, содержащего большее число состояний. Лемма 7.1 тогда позволяет сформулировать следующую теорему.

Теорема .7.1 предполагает, что автомат М может быть определен из автомата Жег состояниями посредством перечисления всех правильных группировок автомата Ж, имеющих мощность г или меньше, и выбора из них наименьшей. Если задана наименьшая правильная группировка, или минимальная правильная группировка, то автомат, квазиэквивалентный автомату Ж, может всегда быть построен описанным ранее способом; этот автомат является минимальной формой автомата Ж. Хотя этот метод и дает решение, он очень трудоемок во всех случаях, кроме наиболее тривиальных, поскольку требует перечисления правильных группировок. В следующем параграфе будет получен ряд результатов, которые позволят отчасти облегчить задачу такого перечисления.

Теорема 7.2. Каждое множество в правильной группировке автомата М должно быть или С-множеством, или подмножеством С-множества автомата М,

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

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

Алгоритм 7.1. Даны все совместимые пары автомата М; требуется определить все С-множества автомата М. (1) Пусть первый перечень множеств состояний состоит из всех совместимых пар автомата Ж и из отдельных состояний, не принадлежащих ни к одной из совместимых пар. Полагаем k = 2.

(2) Для каждого множества состояний [о/. Oi.....oi,

содержащихся в {k - 1)-м перечне, выполняем следующие операции. Определяем I состояний автомата М, скажем О; , Oj.....Oj таких, что Oj {d=\, 2...../) не включено в данное множество, и таких, что каждое О; образует совместимую пару с каждым состоянием из этого множества. Заменяем множество [о, Oi.....о,-} / множествами [о,

Oi.....Oi, Oyj, d=\, 2...../. Если / = 0. то заменим

множество {о/, О/. О/} самим собой. (3) Исключаем

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

С (ft - 1)-м, то ОН является перечнем всех С-множеств автомата М.

Выполнение алгоритма 7.1 облегчается построением матрицы совместимости, обозначаемой [С], элемент (г, J) которой равен 1, если (о. Oj] или {Oj, а] -совместимые пары состояний, и О в противном случае. По построению,

если в каждой строке о,-, Oi,

Oi содержится 1 в ка-

ком-либо данном столбце Оу, то О; образует совместимые пары с каждым состоянием из множества а;, о,, .. ., oJ.

Следовательно, если {о,, а,-.....а,--множество в (ft - 1)-м

перечне и если строки ог, Oi.....О/ матрицы совмещений содержат единицу в столбце О/, множество [а,, Ог, . . . 0/1 должно быть заменено множеством {о,, О/, ...

.... 01, О;}.

В качестве примера рассмотрим автомат /432, изображенный на рис. 7.1. В таблице 7.2 получены все совместимые пары автомата /432, из которых может быть составлен первый перечень:

{1,2}, {1,3}, {1,5}. {2,3}, {2,4}, {2.5}, {3,5}, {3,6}, {4,6}.

Матрица совмещений для /432, которая может быть построена непосредственно по первому перечню, представлена выражением (7.1):

= 3 4 5

4 О 1 О О О 1

(7.1)

Из этой матрицы и первого перечня можно найти второй перечень:

(1, 2, 3}, {1. 2. 5}, {1, 3. 5}, {2, 3, 5}, {2. 4}. {3. 6}. {4, 6}.