индекс класса, в который переходит цифровой автомат из этого состояния.
Таким образом доопределяются неопределённые переходы исходного автомата.
Нормализованный автомат является эквивалентным любому из
минимизированных автоматов и не имеет, как минимум, ни одной пары
совместимых состояний. В соответствии с изложенной методикой минимизации
получаются либо полностью определённые, либо частичные нормализованные
автоматы. У полностью определённых автоматов класс конечной
совместимости не пересекаются, поэтому нормализованный автомат является
единственным и процесс минимизации этим заканчивается. В случае получения
частичного автомата классы i - совместимости пересекаются. Это приводит к
тому, что нормализованный автомат может описываться конечным количеством
вариантов таблиц или графов. В случае частичных автоматов часто
отказываются от достижения абсолютной минимизации и ограничиваются
нахождением нормализованного автомата и его эвристическим
доопределением.
Таким образом, основной алгоритм минимизации автомата Мили состоит
из следующих шагов:
1 Распространение неопределённости выходов на переходы автомата.
2 Исключение недостижимых состояний.
3 Определение классов совместимости и построение нормализованного
автомата.
4 Минимизация нормализованного автомата.
Для полностью определённого цифрового автомата отсутствует
последниё шаг алгоритма.
Для сложных автоматов возможно изменение очерёдности выполнения
шага 2 и шага 3 этого алгоритма, поскольку для минимизированного
нормализованного автомата определение недостижимых состояний требует
меньших затрат труда и времени.