10.6. Минимизация автоматов
С утилитарной точки зрения интерес представляет только зависимость между входами и выходами конечного автомата, а роль его состояний сводится исключительно к участию в формировании этих зависимостей в качестве промежуточных переменных. Следовательно, любая совокупность состояний, обеспечивающая требуемые зависимости между входом и выходом, может быть выбрана в качестве множества состояний автомата. В то же время этот выбор естественно подчинить определенным целям, например, минимизации числа состояний или оптимизации автомата в каком-либо смысле. Следует иметь в виду, что с уменьшением числа состояний уменьшается и количество требуемых элементов памяти, но это может привести к усложнению комбинационной схемы автомата. Поэтому синтез наиболее экономичного автомата часто требует поиска удачного компромисса между сложностью его комбинационной и запоминающих частей.
Минимизация числа состояний полных автоматов связана с отношением эквивалентности. Пусть автоматы М1 и М2, находящиеся соответственно в начальных состояниях и (обозначения М1 и М2 могут относиться к одному и тому же автомату), под воздействием любой входной последовательности выдают одинаковые выходные последовательности, т. е. автоматы М1 и М2 в данных состояниях и неразличимы по внешним входам. Такое отношение между одного и того же или двух разных автоматов обладает ciioi"k'ih;imii рефлексивности, симметричности и транзитивности, следовательно, оно является отношением эквивалентности состояний. Если состояния не эквивалентны, то их называют различимыми. Легко доказать справедливость следующих положений:
1) состояния и автомата явно различимы, если различаются соответствующие им строки в таблице выходов;
2) состояния и автомата явно эквивалентны, если соответствующие им строки в таблице переходов и таблице выходов одинаковы или становятся одинаковыми при замене каждого номера на номер (или наоборот).
пример. для автомата, граф которого изображен на рис. 11.5а, общая таблица переходов имеет вид:
x(v) s(v) |
0 |
1 |
2 |
|
а) |
б) |
0 |
1/0 |
4/0 |
4/1 |
|||
1 |
5/1 |
1/1 |
4/1 |
|||
2 |
1/0 |
1/1 |
6/1 |
|||
3 |
3/1 |
2/0 |
0/1 |
|||
4 |
1/1 |
4/0 |
4/1 |
|||
5 |
1/0 |
5/1 |
4/1 |
Рис. 11.5. Граф конечного автомата (а) и его сокращенная форма (б). |
||
6 |
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}.
Объединяя эквивалентные состояния в автомате М1, получаем эквивалентный автомат М2 с меньшим числом состояний, который в любом состоянии нельзя отличить от исходного, наблюдая сигналы на выходах. Очевидно, автоматы М1 и М2 являются эквивалентными, если каждому состоянию автомата М1 соответствует, по крайней мере, одно эквивалентное ему состояние автомата М2, и если каждому состоянию автомата М2 соответствует хотя бы одно эквивалентное ему состояние автомата М1.
Эквивалентные состояния, например, и удобно объединять по общей таблице переходов, вычеркивая строку и заменяя везде в числителе числа на . После объединения пар явно эквивалентных состояний может оказаться возможным снова обнаружить такие состояния, которые также объединяются с помощью аналогичной процедуры. В результате последовательного объединения приходим к сокращенной таблице переходов, которой соответствует сокращенный автомат, эквивалентный исходному, но имеющий меньшее число состояний. Так, для рассматриваемого примера получаем последовательно:
-
x(v)
s(v)
0
1
2
x(v)
s(v)
0
1
2
0 (4)
1/1
0/0
0/1
0 (4)
1/1
0/0
0/1
1 (5)
1/0
1/1
0/1
1 (5)
1/0
1/1
0/1
2
1/0
1/1
6/1
2 (6)
1/0
1/1
2/1
3
3/1
2/0
0/1
3
3/1
2/0
0/1
6
1/0
1/1
2/1
Первая таблица соответствует объединению пар эквивалентных состояний {0, 4} и {1, 5}, а вторая - объединению пары {2, 6}. Сокращенный автомат содержит только четыре состояния (рис. 11.5б).