Т1 Т2 … Тm = = {t1, t2, … , tp}. Клетка таблицы пуста или содержит один из двух знаков: × или •. Часть А содержит только знаки ×, а часть В – и те, и другие. На пересечении строки Si и столбца qj в части А имеется знак ×, если и только если состояние qj принадлежит множеству Si. На пересечении строки Si и столбца tk имеется знак ×, если и только если tk Si. На пересечении строки Si и столбца tl имеется знак •, если и только если tl принадлежит Ti, соответствующему Si.

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

Таблица 24.9

Обобщенная таблица покрытия

Совместимые				A					B
множества	1	2	3	4	5	6	{1, 2}	{2, 4}	{3, 5}	{3, 6}	{4, 6}
{1, 2, 3, 5}	×	×	×		×		×	•	×	•	•
{2, 4}		×		×				×
{3, 6}			×			×				×
{4, 6}				×		×	•		•		×
{1, 2, 3}	×	×	×				×			•	•
{1, 2, 5}	×	×			×		×	•
{1, 3, 5}	×		×		×			•	×	•
{2, 3, 5}		×	×		×				×		•
{1, 2}	×	×					×
{1, 3}	×		×							•
{2, 5}		×			×
{3, 5}			×		×				×

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

1.Каждый столбец части А имеет знак × хотя бы в одной из этих строк, т. е. искомая совокупность подмножеств должна покрывать все множество состояний.

2.Если какая-то строка из данной совокупности имеет знак • в части В, то столбец, содержащий этот знак, имеет знак × хотя бы в одной из строк данной совокупности, т. е. искомая совокупность должна обладать свойством правильной группировки, которое заключается в том, что любое непосредственно производное множество от любого элемента правильной группировки должно быть подмножеством некоторого элемента этой же группировки.

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

167

1. Если в части А имеется столбец с единственным знаком ×, то строка, содержащая в данном столбце этот знак, вносится в текущее решение и удаляется из таблицы вместе со всеми столбцами, где она имеет знак ×.

2.Если i-я строка имеет знак × везде, где такой знак имеет j-я строка, а j-я строка имеет знак • везде, где знак • имеет i-я строка, то j-я строка удаляется. Нетрудно видеть, что это действие представляет собой то же самое, что и описанное выше удаление некоторых совместимых множеств перед построением таблицы.

3.Если i-й столбец имеет знак × везде, где имеет такой знак j-й столбец из части А, то i-й столбец удаляется.

4.Если из какого-то столбца части В при включении строки в решение

исчез хотя бы один знак •, то этот столбец переводится в часть А и из него удаляются все знаки •.

5. Если в результате удаления строк в некотором столбце части В остались только знаки •, то строки, содержащие эти знаки, удаляются.

Если ни одно из перечисленных условий не выполняется, то выбирается столбец в части А с минимальным числом знаков × и при формировании текущего решения в первую очередь выбирается строка с максимальным числом знаков ×. Если таких строк несколько, выбирается та, которая имеет наименьшее число знаков •. Выбранная строка удаляется из таблицы и удаляются столбцы, имеющие знак × в этой строке.

Пусть исходной таблицей является табл. 24.9. Выбираем столбец 4 как содержащий минимум знаков ×. Строки {2, 4} и {4, 6} имеют одинаковое число знаков ×, но строка {2, 4} не содержит знаков •, и поэтому в текущее решение включаем {2, 4}. После соответствующего преобразования согласно правилам редукции получаем табл. 24.10. В этой таблице выбираем столбец 6 и покрывающую его строку {3, 6}. Табл. 24.10 преобразуется в табл. 24.11.

Таблица 24.10 Результат первого шага преобразования табл. 24.9

Совместимые		A			B
множества	1	3	6	{1, 2} {3, 5}		{3, 6}	{4, 6}
{1, 2, 3, 5}	×	×		×	×	•	•
{3, 6}		×	×			×
{4, 6}			×	•	•		×
{1, 2, 5}	×			×
{1, 3, 5}	×	×			×	•
{3, 5}		×			×

В части А табл. 24.11 остался один столбец, который покрывается тремя строками. Видно, что для его покрытия не стоит выбирать строку {1, 2, 3, 5}, так как согласно правилу 4 в части А появляется новый сто лбец, соответствующий множеству {4, 6}, который тоже должен быть покрыт.

168

Поэтому выбираем строку {1, 2, 5}. Полученная правильная группировка {1, 2, 5}, {2, 4}, {3, 6} является минимальной. Действительно, обратившись к дереву поиска, изображенному на рис. 24.2, видим, что вернувшись в вершину 6 и заменив множество {3, 6} на множество {4, 6}, не получим группировки с двумя элементами. Вернувшись же в начальную вершину 4, можно получить

единственную двухэлементную		группировку			{1, 2, 3, 5}, {4, 6}, которая не
является правильной.
				Таблица 24.11
	Результат преобразования табл. 24.10
	Совместимые		A		B
	множества		1	{1, 2}	{3, 5}	{4, 6}
	{1, 2, 3, 5}		×	×	×	•
	{4, 6}			•	•	×
	{1, 2, 5}		×	×
	{1, 3, 5}		×		×

В результате минимизации автомата, представленного табл. 24.7, получаем автомат с тремя состояниями, таблицей переходов и выходов которого является табл. 24.12.

4 –––{2,4}––– 6 –––{3,6}––– 1 –––{1,2,3,5}–––

––{4,6}––– ––{1,2,5}––– решение

–––{4,6}–––

–––––{1,3,5}–––

Рис. 24.2. Дерево поиска минимальной правильной группировки

Таблица 24.12 Таблица переходов и выходов минимального автомата

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

169