Абстрактные цифровые автоматы (стр. 4 из 5)
Построим автомат Мура: SB={XB, AB, YB, B, B, a0B}, у которого XB=XA; YB=YA.
Для определения ABкаждому состоянию as
АAпоставим в соответствие множество Asвсевозможных пар вида (as, yg)Функцию выходов Bопределим следующим образом. Каждому состоянию автомата Мура SB, представляющему собой пару вида (as,yg), поставим в соответствие выходной сигнал yg.
Если в автомате Мили SAбыл переход A (am, xf) = asи при этом выдавался выходной сигнал A (am,xf) =yg, то в SBбудет переход из множества состояний Am, порождаемых am, в состояние (as,yg) под действием входного сигнала xf.
В качестве начального состояния a0Bможно взять любое из состояний множества A0, которое порождается начальным состоянием a0 автомата SA. При этом выходной сигнал в момент времени t=0 не должен учитываться.
Рассмотрим пример. Пусть задан автомат Мили (табл.1.10.)
| Таблица 10 | Таблица 11 | ||||
| A | x1 | x2 | XА | x1 | x2 |
| a0 | a2/y1 | a0/у1 | a0b0 | a2/y1b01 | a0/y1b02 |
| a1 | a0/y1 | а2/y2 | a1 | a0/y1 b11 | а2/y2b12 |
| a3 | a0/y2 | a1/y1 | a2 | a0/y2b21 | a1/y1b22 |
Поставим в соответствие каждой паре а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и аsK-эквивалентны, если (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 |
Выполним разбиение 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.