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

Для задания конечного автомата необходимо описать все элементы мно- жества A=(X,Y,Z, , ), т.е. входной, выходной и внутренний алфавиты, а также функции переходов и выходов. При этом наиболее часто используются таблич- ный, графический и матричный способ. Ниже эти способы будут рассмотрены подробнее.

На практике наибольшее распространение получили два класса автома-

тов - автоматы Мили (Mealy) и автоматы Мура (Moore).

Автомат Мили функционирует по схеме (2.11 – 2.12). То есть и состояние автомата, и выходной сигнал зависят от входного сигнала и предыдущего со- стояния.

Таблица 2.2

Таблица 2.3

При другом способе задания конечного автомата используется понятие направленного графа. Граф автомата представляет собой набор вершин, со- ответствующих различным состояниям автомата и соединяющих вершин дуг графа, соответствующих тем или иным переходам автомата. Если входной сигнал xkвызывает переход из состояния ziв состояние zj, то на графе авто- мата дуга, соединяющая вершину ziс вершиной zj, обозначается xk. Для того чтобы задать функцию выходов, дуги графа необходимо дополнительно от- метить соответствующими выходными сигналами.

Граф автомата Мили, заданного таблицами 2.2 и 2.3, показан на рис.

2.12.

Рис. 2.12. Граф автомата Мили, соответствующий таблицам 2.2 и 2.3

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

состояниям, а столбцы - состояниям перехода. Элемент cij = xkсоответствует входному сигналу xk, вызывающему переход из состояния ziв состояние zj. Если переход из состояния ziв состояние zjпроисходит под действием не- скольких сигналов, элемент матрицы cijпредставляет собой множество вхо- дов для этого перехода, соединённых знаком дизъюнкции. Матрица выходов D=|| dij ||строится аналогично, но ee элемент dij = ySсоответствует выходному сигналу yS, выдаваемому при переходе. Для рассматриваемого автомата Ми- ли матрицы имеют вид:

x 2

C1 = x1

X1

- x1

- x 2

x 2 -

Y 1

D1 = y 1

Y 2

- y 1

- y 2

y 1 -

Автомат Мура функционирует несколько иначе.

Функция переходов у него имеет тот же вид, как и у автомата Мили, т.е. (2.11). Но функция выходов не зависит от входного сигнала, а является функцией только текущего состояния:

y(tj) = y[ z(tj)].(2.13) Рассмотрим табличный способ задания автомата Мура с пятью состоя- ниями, двумя входными и тремя выходными сигналами. Ниже приведены

таблица переходов (табл. 2.4) и таблица выходов (табл. 2.5).

Таблица 2.5

Графическое отображение автомата Мура практически аналогично отображению автомата Мили, однако значение выходного сигнала обычно размещается около соответствующей вершины.

Граф автомата Мура, заданного таблицами 2.4 и 2.5, показан на рис.

2.13.

Рис. 2.13. Граф автомата Мура, соответствующий таблицам 2.4 и 2.5

При матричном задании конечного автомата Мура матрица переходов аналогична соответствующей матрице автомата Мили, а выход описывается вектором выходов. Для рассматриваемого автомата Мура эти объекты имеют вид:

- x1

- x 2 -

Йy 1 щ

К ъ

- x 2 -

C2 = - x 2 -

- x1

- x1

Кy 1 ъ

D2 = кy 3 ъ

К ъ

X 2 - x1 - -

X 2 - x1 - -

Кy 2 ъ клy 3 ъы

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

По характеру отсчёта времени конечные автоматы делятся на син- хронные и асинхронные. Автомат считается синхронным, когда моменты t0, t1 t2(поступления входных сигналов, изменения состояний и выдачи выход- ных сигналов), определяются принудительно синхронизирующими сигнала- ми (заранее определены). Реакция автомата на каждое значение входного сигнала заканчивается за один такт синхронизации. Асинхронные автоматы не имеют «жесткой» тактности; они изменяют свои состояния при поступле- нии входных сигналов, которые могут появляться в произвольные моменты времени из некоторого интервала.

Пример 2.4

Простейшим примером, который адекватно формализуется в виде ко- нечного автомата, является автомат для продажи напитков. Допустим, ав- томат принимает монеты достоинством 1, 2 и 5 руб. и отпускает стакан на- питка стоимостью 5 руб. Его можно представить, как конечный асинхрон- ный автомат Мили с множеством состояний Z={0, 1, 2, 3, 4}.Входной алфа- вит автомата: X={1, 2, 5}, выходной алфавит Y={0, 1},где 0соответствует ситуации «напиток не отпускается», а 1 –ситуации «напиток отпускается».

Функция переходов j(t)определяется соотношением:

z(ti) = mod[z(ti-1) + x(ti)],5,

а функция выходов y– соотношением:

м0, y(t i ) = н

О 1,

Если

Если

z(t i -1 ) + x(t i ) Ј 4,

z(t i -1 ) + x(t i ) > 4

Построим таблицы переходов и выходов рассматриваемого автомата.

Таблица выходов

Граф автомата будет иметь вид:

Матричное задание автомата:

C П =

5 1

5 -

5 -

Ъ 5 -

1 Ъ 2 Ъ 5 -

2 - -

1 2 -

- 1 2

- - 1

- - -

1 0

1 -

DП = 1 -

1 -

1 -

0 - -

0 0 -

- 0 0

- - 0

- - -