2	3 4 5	6			2	3 4 5	6			2	3 4 5	6
1 1 1 0 0			1		1 1 1 0 0			1		1 1 1 0 0				1
	1 1 1	0	2	,		1 1 1	0	2	,		1 1 1	0		2	.
	1		3			1 1		3			1 1	1		3
			4					4			1			4
						1 1						1
			5				1	5				1		5

Множество Si называется совместимым множеством, если все состояния в нем попарно совместимы. Совместимое множество Si называется максимальным совместимым множеством, если оно не содержится ни в каком другом совместимом множестве в качестве подмножества. К совместимым множествам относятся также все одноэлементные подмножества множества состояний.

Отношение совместимости на множестве состояний частичного автомата может быть представлено в виде неориентированного графа, вершинам которого соответствуют состояния и две вершины связаны ребром, если и только если соответствующие состояния совместимы. Этот граф назовем графом совместимости состояний. Дополнительный по отношению к нему граф является графом несовместимости состояний. Поиск всех максимальных совместимых множеств состояний любого автомата сводится к поиску всех максимальных независимых множеств в графе несовместимости, построенном для заданного автомата. Для решения этой задачи можно использовать метод, описанный в гл. 6, в результате применения которого получим множества

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

Достижимая верхняя граница т числа всех максимальных совместимых множеств для автомата с числом состояний γ так же, как и наибольшее число всех максимальных независимых множеств в графе, приведенное в гл. 6, выражается следующими формулами: где k – некоторое целое положительное число:

т= 2 · 3k – 1, если γ = 3k – 1;

т= 3 · 3k – 1, если γ = 3k;

т= 4 · 3k – 1, если γ = 3k + 1.

24.3.Нахождение минимальной правильной группировки

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

У т в е р ж д е н и е 24.2. Непосредственно производное от совместимого множества есть совместимое множество.

163

Действительно, допустим обратное: пусть для некоторого автомата М подмножество Si множества состояний является совместимым множеством, а непосредственно производное от него Sj – несовместимое множество. Тогда существует последовательность, допустимая для некоторых состояний qk, ql Si, которая вызывает различные заключительные выходные символы у автомата М при начальных состояниях соответственно qk и ql, что противоречит определению совместимости состояний.

Из утверждения 24.2 вытекает следующее.

У т в е р ж д е н и е 24.3. Совокупность всех максимальных совместимых множеств есть правильная группировка.

Действительно, пусть S = {S1, S2, … , Sm} – совокупность всех максимальных совместимых множеств некоторого автомата М. Если бы S не была правильной группировкой, то существовало бы некоторое совместимое

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

Из утверждения 24.3 следует, что правильную группировку можно формировать как некоторую совокупность совместимых множеств. Иногда совокупность всех максимальных совместимых множеств является минимальной правильной группировкой, но чаще всего это не так. Например, автомат, таблицей переходов и выходов которого является табл. 24.5, имеет три максимальных совместимых множества: {1, 2, 3, 4}, {2, 3, 4, 5} и {3, 4, 5, 6}, тогда как минимальной правильной группировкой для него является {{1, 2, 3}, {4, 5, 6}} и ни одна совокупность двух максимальных совместимых множеств не является правильной группировкой. Таблицей переходов и выходов минимального автомата, реализующего данный автомат, является табл. 24.6.

Таблица 24.6 Результат минимизации автомата, заданного табл. 24.5

1	а1	а2	а3
	1,1	2,1	1,1
2	1,0	2,0	2,1

Минимальное число состояний γ′ автомата, реализующего заданный автомат М с числом состояний γ, находится в следующих границах:

α(G) ≤ γ′≤ min(γ, m),

(24.1)

где α(G) – мощность наибольшего независимого множества графа G совместимости состояний; т – число всех максимальных совместимых множеств автомата М. Эта оценка полезна при поиске минимальной правильной группировки.

164

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

Для каждого совместимого множества Si (максимального или немаксимального) построим множество Ti ={ti1 ,ti2 ,...,tik }, элементами которого

являются подмножества множества состояний Q, обладающие следующими свойствами:

1) tij (j = 1, 2, … , k) является непосредственно производным множеством

от Si;

2) никакое tij (j = 1, 2, … , k) не содержится ни в Si, ни в каком др угом til Ti в качестве подмножества;

3) |ti j | > 1 для всех j = 1, 2, … , k.

Если Sg Sh, a Tg Th, то Sg можно исключить из рассмотрения. Действительно, пусть получена правильная группировка, содержащая Sg. Заменив Sg на Sh, получим правильную группировку с тем же числом элементов.

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

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

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

Максимальными совместимыми множествами для этого автомата являются {1, 2, 3, 5}, {2, 4}, {3, 6} и {4, 6}. Все совместимые множества Si с соответствующими Ti представлены в табл. 24.8. Из этой таблицы видно, что для сокращения перебора надо удалить все одноэлементные множества Si, у которых по определению соответствующие Ti всегда пусты, а в данном случае для каждого одноэлементного множества Si найдется двухэлементное

165

множество Sj Si, для которого		Tj = .		Кроме того, удаляются множества
S11 = {1,5} и S12 = {2,3}, поскольку S11 S6, T11 = T6 и S12 S8, T12 = T8.
				Таблица 24.7
Таблица переходов и выходов автомата, подлежащего минимизации
1	а1		а2	а3	а4
	–,–		3,1	4,1	2,1
2	4,0		–,–	–,–	–,–
3	6,0		6,1	–,–	–,–
4	–,–		6,0	1,0	5,1
5	–,–		–,–	2,1	–,–
6	3,0		–,–	2,0	3,1

Таблица 24.8 Совместимые множества

i	Si	Ti
1	{1, 2, 3, 5}	{4, 6}, {3, 6}, {2, 4}
2	{2, 4}
3	{3, 6}
4	{4, 6}	{1, 2}, {3, 5}
5	{1, 2, 3}	{4, 6}, {3, 6}
6	{1, 2, 5}	{2, 4}
7	{1, 3, 5}	{3, 6}, {2, 4}
8	{2, 3, 5}	{4, 6}
9	{1, 2}
10	{1, 3}	{3, 6}
11	{1, 5}	{2, 4}
12	{2, 3}	{4, 6}
13	{2, 5}
14	{3, 5}
15	{1}
16	{2}
17	{3}
18	{4}
19	{5}
6	{6}

Для выполнения второго этапа, осуществляющего комбинаторный поиск, строится обобщенная таблица покрытия. Пусть в результате выполнения первого этапа получена совокупность совместимых множеств S1, S2, … , Sm и соответствующие им множества Т1, Т2, … , Тm. Строкам обобщенной таблицы покрытия соответствуют совместимые множества, а множество столбцов делится на две части: часть А и часть В. Столбцам части А соответствуют состояния заданного автомата, а столбцам части В – элементы множества

166