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

 

Часто при выполнении абстрактного синтеза вводятся избыточные состояния, эквивалентность которых не является очевидной. Избыточное количество состояний может привести к применению лишних триггеров, что усложнит КС1 и КС2. Поэтому очень важно выполнять минимизацию числа состояний перед его структурным синтезом.

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

Определение Два состояния a_s и a_m являются эквивалентными, если
d(a_s, E) = d(a_m, E), где d - функция перехода, E – входное слово произвольной длины.

Другими словами, состояния эквивалентны, если в ответ на одни и те же входные слова вырабатывается одна и та же последовательность состояний, независимо от того в каком из двух состояний a_s или a_m находился автомат в начальный момент времени. Если два состояния эквивалентны, то одно состояние можно заменить на другое.

Кроме эквивалентных состояний существует понятие k-эквивалентных состояний: 1-эквивалентные, 2-эквивалентные и т.д.

Определение Два состояния a_s и a_m являются k-эквивалентными, если
d(a_s, Ek) = d(a_m, Ek), где d - функция перехода, Ek – входное слово длины k.

 

Алгоритм минимизации:

1. Находится последовательно разбиения П₁, П₂, … П_К, П_К+1 состояний автомата до тех пор пока на каком-то К+1 шаге П_К.+1 станет равно П_К. В этом случае полученное к-эквивалентное разбиение будет представлять собой полностью эквивалентные классы.

2. В каждом классе эквивалентности выбирают по одному состоянию, которые образуют новое множество состояний минимизированного автомата.

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

4. Если множество состоит из одного состояние, то у него нет эквивалентных состояний. Если все состояния входят в отдельные множества из одного состояния, то автомат нельзя минимизировать.

5. Разбиение на множества начинается с 0-эквивалентного класса. В данном случае в одни множества попадают состояния с одинаковыми выходными сигналами.