2.Автомат Мили

Выходной символ автомата Мили в момент времени t определяется функцией выходов

w(t)=[s(t),v(t)]. (3)

Таким образом, функция выходов автомата Мили реализует отображение некоторого подмножества D_ SV декартова произведения SV в множество W.

Напомним, что декартово произведение множества A и B, обозначаемое AxB, есть множество .

Иногда, для краткости используют обозначение: s⁺=s(t+1), s=s(t), v=v(t), w=w(t). Тогда функция переходов автомата Мили запишется в виде s⁺=(s,v), а функция выходов в виде w=(s,v).

Автомат называется полностью определенным, если D_=D_=SV. В противном случае автомат называется частичным. Иными словами, у полностью определенного автомата области определения функций [,] и  [,] совпадают с декартовым произведением SV, а у частичного автомата эти функции определены на подмножествах D_ и D_ множества SV.

Способность автомата фиксировать состояния, представляющие классы входных последовательностей (события), называют памятью автомата. Каждое состояние sS автомата представляет некоторый класс эквивалентности {v(0)v(1)v(2)…v(k)}_s входных последовательностей, поскольку поведение автомата в любой момент времени t зависит только от класса, т.е. s(t), и входного воздействия v(t). Такой подход позволяет устранить время как явную переменную и выразить выходные символы как функцию состояний и входных символов в данный момент времени, что находит выражение в общей записи модели A абстрактного автомата Мили:

A = <V,W,S,,,s(0)>, (4)

где

V,W,S - алфавиты входных, выходных символов и символов состояний соответственно;

,  - функции переходов и выходов соответственно;

s(0) - начальное состояние.

3.Способы описания конечных автоматов

Для описания конечных цифровых автоматов можно использовать стандартные (автоматные) языки и начальные языки.

3.1 Стандартные или автоматные языки описания.

Они описывают функции переходов и выходов в явном виде, а именно в виде:

1. таблиц переходов и выходов;

Из определения автомата следует, что его всегда можно задать таблицей с двумя входами, содержащей m строк и n столбцов, где на пересечении столбца q( состояния автомата) и строки а (входные сигналы) стоят значения функций φ() (a_i,q_j) (функция переходов); \|/ ( )(a_i,q_j)(функция выходов).

Таблица 1

2. Графа, представляющего наглядно функции  и ..

Другой способ задания конечного автомата — графический. При этом способе состояния автомата изображают кружками, в которые вписывают символы состояний q_j (j= 1,..., п). Из каждого кружка проводится m стрелок

( ориентированных рёбер) взаимно-однозначно соответствующих символам входного алфавита X(V). Стрелке, соответствующей букве а_i X и выходящей из кружка q_j Q(S), приписывается пара (а_{i ,}\|/ (a_i,q_j) , причем эта стрелка ведет в кружок, соответствующий φ (a_i,q_j)

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

Автомат Мура

Абстрактный автомат Мура это частный случай автомата Мили (4), когда выходной символ зависти только от состояния автомата, а именно функция выходов автомата Мура:

w=(s) (5)

Для каждого автомата Мили можно построить эквивалентный автомат Мура, реализующий точно такой же алфавитный оператор. Пусть A = <V,W,S,,,s(0)> автомат Мили. В качестве состояний эквивалентного автомата Мура возьмем пары . Тогда функция выходов эквивалентного автомата Мура

, (6)

а функция переходов

. (7)