Контрольная работа: Абстрактные цифровые автоматы
b22
Поставим в соответствие каждой паре аi /xk состояние Ьik (i-номер состояния, k-номер входного сигнала), с учетом b0 .
Составим таблицу переходов автомата Мура, руководствуясь следующими правилами:
1) Выпишем из таблицы 1.11 состояния автомата Мили и соответствующие каждому из них множества состояний автомата Мура (bik ):
а0 = {b0 , b02 , b11 , b21 }; a1 = {b22 }; а2 = {b01 , b12 };
2) Если состояние автомата Мура bik входит в множество, соответствующее состоянию аp автомата Мили, то в строку таблицы переходов автомата Мура для состояния bik следует записать строку из таблицы переходов автомата Мили, соответствующую состоянию ар (из 1.10.).
3) Функцию выходов автомата Мура определим следующим образом: B (bik ) =A (аi , xk ). Для начального состояния b0 значение выходного сигнала можно выбрать произвольно, но порождаемый начальным состоянием a0 (с учетом понятия эквивалентности состояний). Результирующая таблица переходов и выходов автомата Мура эквивалентного автомату Мили, заданному таблицей 1.10 представлена в таблице 1.12.
4) Найдем в таблице 1.12 эквивалентные состояния и удалим их (заменим на представителя класса эквивалентности).
Если выходной сигнал возле b0 доопределить y1 , то окажется, что в данной таблице переходов находится 3 эквивалентных состояния (b0 ,b11 ,b02 ). Заменив класс эквивалентности одним представителем (b0 ), получим окончательную таблицу переходов (табл.1.13).
Таблица 1.12
| x1 | x2 | Y | |
| b0 | b01 | b02 | y1 |
| b01 | b21 | b22 | y1 |
| b02 | b01 | b02 | y1 |
| b11 | b01 | b02 | y1 |
| b12 | b21 | b22 | y2 |
| b21 | b01 | b02 | y2 |
| b22 | b11 | b12 | y1 |
Таблица 1.13.
| x1 | x2 | У | |
| b0 | b01 | b0 | y1 |
| b01 | b21 | b22 | y1 |
| b12 | b21 | b22 | y2 |
| b21 | b01 | b0 | y2 |
| b22 | b0 | b12 | y1 |
Изложенные методы взаимной трансформации автоматов Мили и Мура показывают, что при переходе от автомата Мура к автомату Мили число состояний автомата не изменяется, тогда как при обратном переходе число состояний в автомате Мура, как правило, возрастает.
Таким образом, эквивалентные между собой автоматы могут иметь различное число состояний, в связи с чем возникает задача нахождения минимального (с минимальным числом состояний) автомата в классе эквивалентных между собой автоматов. Существование для любого абстрактного автомата эквивалентного ему абстрактного автомата с минимальным числом внутренних состояний впервые было доказано Муром.
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 |
|
К-во Просмотров: 332
Бесплатно скачать Контрольная работа: Абстрактные цифровые автоматы
|