Абстрактные цифровые автоматы

контрольная работа

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

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

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

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

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

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

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

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

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

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

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

Таблица 1.14

У

y1

y1

y3

y3

y3

y2

y3

y1

y2

y2

y2

y2

А

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

a12

x2

a10

a12

a5

a7

a3

a7

a3

a10

a7

a1

a5

a2

x2

a5

a7

a6

a11

a9

a11

a6

a4

a6

a8

a9

a8

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

?0={В1, В2, В3};

B1={a1, a2, a8}, В2={а6, а9, а10, а11, а12}, В3={а3, a4, a5, a7}.

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

У

B1

В2

В3

А

a1

a2

a8

a6

a9

a10

a11

a12

a3

а4

a5

a7

х1

В2

В2

В2

В3

В3

B1

В3

B1

В3

В3

В3,

В3

х2

В3

В3

В3

В2

В2

B1

B2

B1

В2

В2

В2

В2

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

?1={С1, С2, С3, С4};

C1={a1, a2, a8}, С2={а6, а9, а11}, С3={ а10, a12}, С4={а3, а4, a5, a7}.

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

У

С1

С2

С3

С4

А

a1

a3

a8

a6

a9

a11

a10

a12

a3

а4

a5

a7

х1

С3

С3

С3

С4

С4

С4

C1

C1

С4

C4

С4

С4

х2

С4

С4

С4

С2

С2

С2

C1

C1

С2

С2

С2

С2

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

?1={D1, D2, D3, D4};

D1={a1, a2, a8}, D2={а6, а9, а11}, D3={ а10, a12}, D4={а3, а4, a5, a7}.

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

Выберем произвольно из каждого класса эквивалентности D1, D2, D3, D4 по одному представителю - в данном случае по минимальному номеру: A={a1, а3, a6, а10}.

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

Таблица 1.15.

У

y1

y3

y2

y2

А

a1

a3

a6

a10

х1

a10

a3

a3

a1

х2

a3

a6

a6

a1

Делись добром ;)