Файл: Баранов, С. И. Синтез микропрограммных автоматов.pdf

в начальные состояния их реакции на любое входное слово совпадают. Можно показать [7], что для любого автомата Мили существует эквивалентный ему автомат Мура и, обратно, для любого автомата Мура существует эквивалентный ему автомат Мили. При описании алгоритмов взаимной трансформации автоматов Мили и Мура в соот­ ветствии с изложенным выше мы будем пренебрегать в автоматах Мура

выходным сигналом, связанным с начальным состоянием (X (cj)). Рассмотрим сначала преобразование автомата Мура в автомат

Мили. Пусть дан автомат Мура

S.4— Z А, Ѵ А, б^, ХА, «і /і),

Функцию выходов Хв определим следующим образом. Если в авто­ мате Мура бл (а,„, Zf) = as и ХА (as) = wg, то в автомате Мили Хв (аіп, Zf) = wg.

Переход от автомата Мура к автомату Мили при графическом спо­ собе задания иллюстрируется рис. 1-7: выходной сигнал (wg), записан­ ный рядом с вершиной (as), переносится на все дуги, входящие в эту вершину. На рис. 1-8 приведен граф автомата Мили S0, эквивалент­ ного автомату Мура S 3 (рис. 1-4).

При табличном способе задания автомата S 4 таблица переходов автомата S B совпадает с таблицей переходов S A, а таблица выходов S B получается из таблицы переходов заменой символа as, стоящего на пересечении строки Zf и столбца ат, символом выходного сигнала we, отмечающего столбец as в таблице переходов автомата S^.

12

Из самого способа построения автомата Мили S B очевидно, что

в состоянии а,п, то он перейдет в состояние as = бд (ат, zf) и выдаст

гласно способу построения функции %в . Таким образом, для входной последовательности длины один поведение автоматов S A и S B пол­ ностью совпадает. По индукции нетрудно показать, что любое вход­ ное слово конечной длины, поданное на входы автоматов 5 л и S B, установленных в состояния ат, вызовет появление одинаковых вы­ ходных слов и, следовательно, автоматы S A и S B эквивалентны.

Прежде чем рассмотреть трансформацию автомата Мили в авто­ мат Мура, наложим на автомат Мили следующее ограничение: у авто-^ мата не должно быть преходящих состояний. Под преходящим будем понимать состояние, в которое при представлении автомата в виде графа не входит ни одна дуга, но которое имеет по крайней мере одну выходящую дугу (пример — состояние ах на рис. 1-3). Итак, пусть задан автомат Мили

■5ц— [А А, Z А, W л , 8Л, ХА, а1А],

S b — И й> %в > W в , 8В, Хв , а1В),

' у которого

Zb = Z a = Ігі> • • • I z/> • • • > zf)>

W B= W A = (tOj, . . . , Wg, . . . , wa).

13

Для определения А в каждому состоянию as £ А л поставим в со­ ответствие множество As всевозможных пар вида (as, wg), где wg — выходной сигнал, приписанный входящей в as дуге (рис. 1-9):

Л = { (“*> Wg) I б (ат, Zf) = as и Х(ат, Z/) = wg}.

Число элементов в множестве A s равно числу различных выходных сигналов на дугах автомата S A, входящих в состояние as.

Множество состояний автомата S B получим как объединение мно­ жеств /ls (s = 1, . . . , М)\

м

Ав и А к.

14

ния а± есть переход под действием сигнала zx в состояние а3 с выда­

Функцию переходов 8В определим как и ранее, в частности из состоя­

автомата Мили, то в качестве начального состояния автомата Мура следует взять порождаемое им состояние Ьъ. На рис. 1-12 приведен граф автомата Мура S 8, эквивалентного автомату Мили на рис. 1-11.

Эквивалентность автоматов S B и S A при преобразовании автомата Мили в автомат Мура на множестве входных слов конечной длины легко доказать по индукции подобно изложенному выше при обратном преобразовании.

15

Изложенные методы взаимной транспозиции моделей Мили и Мура показывают, что при переходе от автомата Мура к автомату Милн число состояний автоматов не меняется, тогда как при обратном пе­ реходе число состояний в автомате Мура, как правило, возрастает. Если, например, от автомата Мура S5 (рис. 1-6), эквивалентного ав­ томату Мили S x (рис. 1-2), перейти вновь к автомату Мили, то полу­ чим автомат Мили S s (рис. 1-13). Вследствие транзитивности отноше­ ния эквивалентности два автомата Мили Sx и S g также будут эквива­ лентны, но у последнего на два состояния будет больше. Таким обра­ зом, эквивалентные между собой автоматы могут иметь различное число состояний, в связи с чем возникает задача нахождения мини­ мального (т. е. с минимальным числом состояний) автомата в классе эквивалентных между собой автоматов. Существование для любого абстрактного автомата 5 эквивалентного ему абстрактного автомата Smin с минимальным числом внутренних состояний впервые было до­ казано Муром.

1-4. Минимизация полностью определенных автоматов

Рассмотрим алгоритм минимизации полностью определенных аб­ страктных автоматов Мили, предложенный Ауфенкампом и Хоном [1 ]. Основная идея этого метода состоит в разбиении всех состояний исходного абстрактного автомата на попарно не пересекающиеся классы эквивалентных состояний и замене каждого класса эквивалент­ ности одним состоянием. Таким образом, получающийся в результате минимальный автомат имеет столько же состояний, на сколько классов эквивалентности разбиваются состояния исходного автомата.

Если ат и as не эквивалентны, они различимы. Более слабой эквива­

^-различимы.

Введенные отношения эквивалентности и /г-эквивалентности реф­ лексивны, симметричны и транзитивны, следовательно, они являются отношениями эквивалентности, а потому могут быть использованы для разбиения множества А состояний автомата на попарно не пере­ секающиеся классы (классы эквивалентности). Соответствующие раз­ биения на классы эквивалентных и /г-эквивалентных состояний будем обозначать я и пк. Разбиение я позволяет определить избыточные эле­ менты в множестве состояний А. Пусть, например, ат и as эквива­ лентны. Это значит, что с точки зрения реакций автомата на всевоз­ можные входные слова неважно, находится автомат в состоянии ат или as, и одно из них, например as,. может быть удалено из множества А. Если каждый класс эквивалентности содержит только одно состоя­ ние, множество А несократимо. Если же один или несколько классов содержат более одного элемента, все элементы, кроме одного в каждом

16