Алгоритм Ауфенкампа-Хона.
В основу метода минимизации состояний автомата положена идея разбиения всех состояний исходного, абстрактного автомата на попарно не пересекающиеся классы эквивалентных состояний и замене каждого класса эквивалентности одним состоянием (представителем данного класса). Образующийся в результате этих преобразований минимальный автомат имеет столько же состояний, на сколько классов эквивалентности разбиваются исходные состояния.
Два состояния автомата 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' определяют на множестве A'xX.
Для этого в таблице переходов и выходов вычеркивают столбцы, соответствующие не вошедшим в множество А' состояниям, а в оставшихся столбцах таблицы переходов все состояния заменяются на эквивалентные из множества А', (на представителей).
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 |
Другое по теме:
Расчет характеристик сигналов и канала связи На современном этапе развития перед железнодорожным транспортом стоят задачи по увеличению пропускной и провозной способности, грузовых и пассажирских перевозок, уменьшению времени оборотов вагонов и повышению производительности труда. Эти зада ...