Минимизация числа состояний автомата

Некоторые состояния, полученные путём анализа реакции автомата на входные сигналы, могут оказаться избыточными. Это может усложнить комбинационную схему автомата, так как от числа состояний зависит число элементов, в которых хранится информация о текущем состоянии. Минимизация особенно важна, если число состояний переходит через степень 2.

Алгоритм минимизации основан на разбиении всех состояний исходного автомата на попарно непересекающиеся подмножества – классы эквивалентности состояний и замене каждого класса одним состоянием.

Определение. Два состояния a_s и a_m являются эквивалентными a_sºa_m, если d(a_s,e)= l(a_m, e), где e — входное слово произвольной длины. Таким образом состояния будут эквивалентны в том случае, если при одном и том же входном слове произвольной длины e, независимо от того в каком из состояний a_s или a_m автомат находился в начальный момент времени, вырабатывается одна и та же последовательность состояний.

Определение. Два состояния a_s и a_m являются k–эквивалентными, если d(a_s,e _k)= l(a_m, e_k), где e_k— входное слово длины k. То есть состояния будут k–эквивалентны, если при одном и том же входном слове длины e_k, независимо от того в каком из состояний a_s или a_m автомат находился в начальный момент времени, выработается одна и та же последовательность состояний. При прохождении k+1 слова состояния a_s и a_m могут оказаться не эквивалентными.

Для минимизации автомата производят последовательность разбиений П₁, П₂, П₃,..., П_k состояний автомата пока на каком-то k+1 шаге не окажется, что П_k+1= П_k. В таком случае П_k=П k–эквивалентные состояния являются эквивалентными. Из каждого класса эквивалентности выбирается по одному состоянию, которое образует минимальное множество состояний автомата. Для определения таблиц переходов и выходов строки, соответствующие не вошедшим состояниям, вычёркиваются, а в оставшихся строках таблицы переходов все состояния заменяются на эквивалентные.

Вводится понятие 0–эквивалентных состояний, состояний которым соответствуют одинаковые выходные сигналы, так как состояния с разными выходными сигналами нельзя объединить в класс эквивалентности.

Проведём минимизацию автомата Мура, заданного выше.

Первое разбиение П₁={A₀, A₁} производится по таблице выходов. В подмножестве A₀ объединяются все состояния, которым соответствуют нулевой выходной сигнал, в A₁ — единичный. То есть A₀={ a₀, a₁, a₂, a₃ }, A₁={ a₄ }. Подмножество A₁ состоит из одного элемента, следовательно, a₄ обязательно войдёт в минимальную таблицу переходов автомата. Для последующих разбиений в строках, соответствующих состояниям из класса A₀, состояния, в которые происходят переходы, заменим на классы 1–эквивалентности в таблице переходов состояния.

Таблица 4.4 - Таблица переходов на первом этапе минимизации.

Одинаковые строки в таблице объединим в классы разбиения B₀ и B₁. П₂={ B₀, B₁ }, где B₀={ a₀, a₁, a₂}, B₁={ a₃ }. Звёздочкой (*) отмечена строка, которая войдёт в минимальную таблицу переходов.

Таблица 4.5 - Таблица переходов на втором этапе минимизации.

П₃={C₀,C₁}, где С₀={ a₀, a₁ }, C₁= { a₂ }.

Таблица 4.6 - Таблица переходов на третем этапе минимизации.

Таким образом, мы получили последнее разбиение

П₄={D₀, D₁}, где D₀={ a₀ }, D₁= {a₁ }.

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

Выполним для автомата Мили минимизацию состояний.

Первое разбиение произведём по таблице выходов автомата Мили.

П₁={A₀, A₁}, A₀={ a₀, a₁, a₂, a₄ }, A₁={ a₃ }.

Таблица 4.7 - Таблица переходов на первом этапе минимизации.

П₂={ B₀, B₁ }, где B₀={ a₀, a₁, a₄}, B₁={ a₂ }

Таблица 4.8 - Таблица переходов на втором этапе минимизации.

П₃={C₀,C₁}, где С₀={ a₀, a₄ }, C₁= { a₁ }.

Таблица 4.8 - Таблица переходов на третьем этапе минимизации.

В данном случае состояния a₀, a₄ являются эквивалентными. Удалим одно из состояний из таблицы переходов.

Таблица 4.9 - Минимальная таблица переходов.

Анализируя первоначальную таблицу переходов и выходов, получим таблицу выходов:

Таблица 4.10 - Таблица выходов.