Контрольная работа: Абстрактные цифровые автоматы
Изложенные методы взаимной трансформации автоматов Мили и Мура
показывают, что при переходе от автомата Мура к автомату Мили число состояний автомата
не изменяется, тогда как при обратном переходе число состояний в автомате Мура,
как правило, возрастает.
Таким образом, эквивалентные между собой автоматы могут иметь
различное число состояний, в связи с чем возникает задача нахождения минимального
(с минимальным числом состояний) автомата в классе эквивалентных между собой автоматов.
Существование для любого абстрактного автомата эквивалентного ему абстрактного автомата
с минимальным числом внутренних состояний впервые было доказано Муром.
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' определяют на множестве 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
|
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 |