1.6 Минимизация числа внутренних состояний автомата

Алгоритм Ауфенкампа-Хона.

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

Два состояния автомата a_m и a_s называются эквивалентными (a_m =a_s), если ? (a_m,X) = ? (a_s,X) для всех возможных входных слов длины X.

Если a_m и a_s не эквивалентны, они различимы. Более слабой эквивалентностью является K-эквивалентность. Состояния a_m и а_s K-эквивалентны, если ? (a_m, Х_k) = ? (a_s, Х_k) для всех возможных входных слов длины К. При минимизации числа внутренних состояний автомата Мили S={X,Y, А, ?,?, а₀} используется алгоритм Ауфенкампа-Хона:

1. Находят последовательные разбиения ?₁,?₂,…,?_k,?_k+1, множества А на классы одно-, двух-,., К-, (К+1) - эквивалентных состояний до тех пор, пока на каком-то (К+1) шаге не окажется, что ?_k=?_k+1. В этом случае К-эквивалентные состояния являются эквивалентными. Число шагов К, при котором ?_k=?_k+1 не превышает N-1, где N - число внутренних состояний автомата.

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

3. Функцию переходов ? и выходов ? автомата S определяют на множестве AxX.

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

4. В качестве а₀ выбирается одно из состояний, эквивалентное состоянию а₀. В частности, удобно принять само состояние а₀.

При минимизации автомата Мура вводится понятие 0-эквивалентности состояний и разбиения множества состояний на 0-классы: 0-эквивалентными называются любые, одинаково отмеченные выходными сигналами, состояния автомата Мура. В качестве примера рассмотрим минимизацию автомата Мура, заданного таблицей переходов и выходов (Таблица 1.14).

Таблица 1.14

Выполним разбиение ?₀:

?₀={В₁, В₂, В₃};

B₁={a₁, a₂, a₈}, В₂={а₆, а₉, а₁₀, а₁₁, а₁₂}, В₃={а₃, a₄, a₅, a₇}.

Построим таблицу разбиения ?₀:

Выполним разбиение ?₁:

?₁={С₁, С₂, С₃, С₄};

C₁={a₁, a₂, a₈}, С₂={а₆, а₉, а₁₁}, С₃={ а₁₀, a₁₂}, С₄={а₃, а₄, a₅, a₇}.

Построим таблицу разбиения ?₁:

Выполним разбиение ?₂.

?₁={D₁, D₂, D₃, D₄};

D₁={a₁, a₂, a₈}, D₂={а₆, а₉, а₁₁}, D₃={ а₁₀, a₁₂}, D₄={а₃, а₄, a₅, a₇}.

Разбиение ?₂ повторяет разбиение ?₁ - процедура разбиения завершена.

Выберем произвольно из каждого класса эквивалентности D₁, D₂, D₃, D₄ по одному представителю - в данном случае по минимальному номеру: A={a₁, а₃, a₆, а₁₀}.

Удаляя из исходной таблицы переходов "лишние" состояния, определяем минимальный автомат Мура (табл.1.15.)

Таблица 1.15.