В основу метода минимизации состояний автомата положена идея разбиения всех состояний исходного, абстрактного автомата на попарно не пересекающиеся классы эквивалентных состояний и замене каждого класса эквивалентности одним состоянием (представителем данного класса). Образующийся в результате этих преобразований минимальный автомат имеет столько же состояний, на сколько классов эквивалентности разбиваются исходные состояния.
Алгоритм
При минимизации числа внутренних состояний автомата Мили используется алгоритм Ауфенкампа-Хона:
1. Находят последовательные разбиения p1, p2, … ,pk, pk+1, множества А на классы одно-, двух-, ..., К-, (К+1) -эквивалентных состояний до тех пор, пока на каком-то (К+1) шаге не окажется, что pk=pk+1. В этом случае К-эквивалентные состояния являются эквивалентными. Число шагов К, при котором pk=pk+1 не превышает N-1, где N- число внутренних состояний автомата.
2. В каждом классе эквивалентности p выбирают по одному элементу (представителю класса), которые образуют множества А' состояний минимального автомата S'.
3. Функцию переходов d' и выходов l' автомата S' определяют на множестве A'xX. Для этого в таблице переходов и выходов вычеркивают столбцы, соответствующие не вошедшим в множество А' состояниям, а в оставшихся столбцах таблицы переходов все состояния заменяются на эквивалентные из множества А', (на представителей).
4. В качестве а'0 выбирается одно из состояний, эквивалентное состоянию а0. В частности, удобно принять само состояние а0.
Пример
Hассмотрим минимизацию автомата Мили, заданного таблицей переходов и выходов
Выполним разбиение p0:
Построим таблицу разбиения:
Выполним разбиение p1:
Выполним разбиение p2:
Разбиение p2 повторяет разбиение p1 - процедура разбиения завершена.
Из него можно перейти к автомату Мура