Автоматное описание управляющего автомата

 

Характерной особенностью начальных языков является то, что они не по­зволяют в явном виде задать функцию переходов. Поэтому для синтеза УА не­обходим переход от начального языка к автоматному языку описания.

Описание автомата на абстрактном уровне позволяет осуществить ана­лиз его функционирования без учёта конкретно реализуемых функций и V

условии.

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

состоянии.

Так как функционирование абстрактного автомата в данном курсовом проекте описывается с помощью модели Мили, то необходимо выделить ха­рак­терные черты данного управляющего автомата.

 

 Модель Мура.

Закон функционирования автомата типа Мура математически задается следующей системой уравнений (1):

                          (1)

где

a(t) – внутреннее состояние автомата в момент времени t (настоящий момент времени);

z (t) – входной сигнал в момент времени t;

w (t) – выходной сигнал в момент времени t;

a (t+1) - внутреннее состояние автомата в момент времени (t+1) (в следую­щий момент времени);

δ - функция переходов;

λ - функция выходов.

Первое уравнение в (1) отражает тот факт, что переход автомата в сле­дующее состояние a(t+1) осуществляется только с приходом входного сигнала (входного символа) z(t) в момент времени t. При этом, то конкретное состоя­ние, в которое перейдет автомат в момент времени (t+1), определятся парой (a_m, z_f), т.е. состоянием автомата a(t) и входным сигналом (символом) z(t) в момент времени t. Функция переходов в автомате типа Мура имеет такой же вид, как и для автомата типа Мили со всеми рассмотренными ранее особенно­стями математической и технической корректности модели.

Второе уравнение в (1) отражает закономерность формирования вы­ходного сигнала (символа) автоматом типа Мура. Из уравнения видно, что выходной сигнал определяется только состоянием автомата в момент времени t и в явном виде не зависит от входного сигнала z(t). Соответствующий со­стоянию a(t) выходной сигнал в автомате Мура формируется на всем протя­жении времени, пока автомат находится в состоянии a(t). В связи с данной особенностью автомата типа Мура говорят, что данный тип автомата форми­рует "длинные" выходные сигналы, которые однозначно определяются тем состоянием автомата, в котором он находится в данный момент времени.

Не смотря на то, что состояние выхода автомата Мура не зависит явно от состояния входа, его можно рассматривать как частный случай автоматов Мили. Действительно, так как для автоматов Мура справедливо

 

a(t) = δ (a(t-1), z(t-1)), (2)

 

то справедливо и следующее соотношение:

 

w(t) = λ (a(t)) = g (a(t-1), z(t-1)). (3)

 

Соотношение (2) показывает, что в автомате Мура выходной сигнал ре­ально зависит от входного сигнала, но только действующего в предыдущий момент времени. Различие между автоматами Мура и Мили состоит в том, что в автоматах Мили выходной сигнал возникает одновременно с вызывающим его входным сигналом, а в автоматах Мура - с опозданием (задержкой) на один такт автоматного времени. Поэтому автоматы Мура можно рассматри­вать как автоматы Мили, имея в виду, что последовательность состояний вы­хода автомата Мили опережает на один такт последовательность состояний выхода автомата Мура.

В теории автоматов доказано, что между автоматами Мили и Мура су­ществует взаимооднозначное соответствие: любой автомат Мили может быть преобразован в эквивалентный ему автомат Мура и наоборот.

23

При переходе от автомата Мура к автомату Мили число состояний ав­томата не меняется, тогда как при обратном переходе число состояний в авто­мате Мура, как правило, возрастает. Таким образом, эквивалентные между со­бой автоматы могут иметь различное число состояний, в связи с чем в теории автоматов возникает задача нахождения минимального (с наименьшим чис­лом состояний) автомата в классе эквивалентных между собой автоматов.

Существование для любого абстрактного автомата эквивалентного ему абстрактного автомата с минимальным числом внутренних состояний впервые было доказано Муром.