Четвёртый этап минимизации

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

Пусть есть автомат, заданный следующей отмеченной таблицей переходов:

Алгоритм минимизации заключается в следующем:

1. Все внутренние состояния разбиваются на группы по числу выходных сигналов. В нашем случае есть два выходных сигнала y ₁ и y ₂ и, следовательно, будет две группы, которые мы обозначим буквами a и b.

2. По таблице переходов автомата определяют, к каким группам принадлежат внутренние состояния, в которые автомат переходит из данного состояния под воздействием каждой буквы входного алфавита. Эти состояния запишем в виде последовательности букв под каждым из состояний автомата. Например, из состояния 0 автомат переходит в состояния 2, 3 и 1, которые принадлежат соответственно к следующим группам a, b и a. Эта последовательность букв (aba) и записывается под состоянием 0.

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

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

Все состояния, входящие в каждую из этих групп, можно заменить одним состоянием той же группы. Взяв в качестве представителей групп состояния 0, 1, 3 и 6 и обозначив их символами a ₀, a ₁, a ₂ и a ₃ соответственно, получим следующую таблицу переходов с минимальным числом внутренних состояний.

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

В полученной таблице колонки, помеченные состояниями a ₀ и a ₂, a ₁ и a ₃ идентичны, что позволяет при минимизации исключить состояния a ₂ и a ₃. В результате получаем таблицу переходов и выходов автомата Мили имеющего два состояния a ₀ и a ₁.