Минимизация автоматов

 

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

Минимизация числа состояний полных автоматов связана с отношением эквивалентности. Пусть автоматы М₁ и М₂ находящиеся в начальных состояниях s_i и s_j (обозначения М₁ и М₂ могут относиться к одному и тому же автомату), под воздействием любой входной последовательности выдают одинаковые выходные последовательности, т. е. автоматы М₁ и М₂ в данных состояниях s_i и s_j неразличимы по внешним выходам. Такое отношение между состояниями одного и того жеили двух различных автоматов обладает свойствами рефлексивности, симметричности и транзитивности, следовательно, оно является отношением эквивалентности состояний. Если состояния не эквивалентны, то их называют различимыми. Легко доказать справедливость следующих положений:

1) состояния s_i и s_j автомата явно различимы, если различаются соответствующие им строки в таблице выходов;

2) состояния s_i и s_j автомата явно эквивалентны, если соответствующие им строки в таблице переходов и таблице выходов одинаковы или становятся одинаковыми при замене каждого номера s_i на номер s_j (или наоборот).

Например, рассмотрим автомат, заданный таблицей переходов.

Таблица 7

x(n) s(n)
	1/1	4/0	4/1
	5/0	1/1	4/1
	1/0	1/1	6/1
	3/1	2/0	0/1
	1/1	4/0	4/1
	1/0	5/1	4/1
	5/0	5/1	2/1

 

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

Объединяя эквивалентные состояния в автомате М₁, получаем эквивалентный автомат М₂ с меньшим числом состояний, который в любом состоянии нельзя отличить от исходного, наблюдая сигналы на выходах. Очевидно, что автоматы М₁ и М₂ являются эквивалентными, если каждому состоянию s_i автомата М₁ соответствует, по крайней мере, одно эквивалентное ему состояние автомата М₂ и если каждому состоянию s_j автомата М₂ соответствует хотя бы одно эквивалентное ему состояние автомата М₁.

Эквивалентные состояния, например, s_i и s_j удобно объединять по общей таблице переходов, вычеркивая строку s_j и заменяя везде в числителе числа s_j на s_i. После объединения пар явно эквивалентных состояний может оказаться возможным снова обнаружить такие состояния, которые также объединяются с помощью аналогичной процедуры. В результате последовательного объединения приходим к сокращенной таблице переходов, которой, соответствует сокращенный автомат, эквивалентный исходному, но имеющий меньшее число состояний. Так, для рассматриваемого примера получаем последовательно автомат М₂, эквивалентный автомату М₁ и автомат М₃, эквивалентный автомату М₂.

Таблица 8

x(n) s(n)
0(4)	1/1	0/0	0/1
1(5)	1/0	1/1	0/1
	1/0	1/1	6/1
	3/1	2/0	0/1
	1/0	1/1	2/1

 

Таблица 9

x(n) s(n)
0(4)	1/1	0/0	0/1
1(5)	1/0	1/1	0/1
2(6)	1/0	1/1	2/1
	3/1	2/0	0/1

 

Табл. 8 соответствует объединению пар эквивалентных состояний {0,4} и {1, 5}, а табл. 9 – объединению пары {2, 6}. Сокращенный автомат содержит только четыре состояния.