Автомат может быть задан различными способами, например, путем словесного описания его функционирования или перечислением элементов множеств X, Y, S, с указанием отношений между ними. При анализе и синтезе конечных автоматов используются стандартные формы представления: таблицы, графы и матрицы. Элементы множеств X, Y, S удобно пронумеровать порядковыми числами, начиная с нуля, например: Х = {0, 1, 2, 3},
Y = {0, 1, 2, 3} и S = {0, 1, 2, 3}. Тогда характеристические функции d и l можно представить двумя таблицами, строки которых соответствуют состояниям, а столбцы - входам. Первая таблица, называемая таблицей переходов, соответствует функции , и ее клетки заполняются номерами состояний s (v +1), в которые переходит автомат при воздействии x(v), и состоянии s(v) в данный тактовый момент. Вторая таблица, называемая таблицей выходов, соответствует функции , и ее клетки заполняются номерами выходов y(v) в данный тактовый момент, которые соответствуют воздействию x(v) и состоянию s(v) в тот же момент. Например, для заданных множеств X, Y, S такие таблицы могут иметь вид:
|
|
|
x(v)
s(v)
|
|
|
|
| x(v)
s(v)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Обе таблицы можно объединить в общую таблицу переходов, если условиться записывать в клетках пары чисел (номер следующего состояния в числителе и номер выхода в знаменателе), т. е.
x(v)
s(v)
|
|
|
|
|
| 3/0
| 2/0
| 1/0
| 3/0
|
| 3/1
| 2/0
| 1/0
| 3/1
|
| 3/1
| 2/0
| 2/1
| 3/1
|
| 3/0
| 0/0
| 0/1
| 1/1
|
Граф автомата строится таким образом, что его вершины соответствуют состояниям, а направленные дуги обозначаются как дизъюнкции входов, под воздействием которых совершается переход из одного состояния в другое по направлению дуги. В знаменателях записываются номера выходов, соответствующие этим переходам.
Пример. На рис. 14.2 показан граф, построенный в соответствии с приведенной выше общей таблицей переходов. Так как из состояния 0 автомат переходит в состояния 1, 2 и 3, то из вершины 0 графа исходят дуги в вершины 1, 2 и 3. При этом переход в состояние 1 совершается под воздействием 2 и ему соответствует выход 0, поэтому дуга из вершины 0 в 1 помечается как 2/0. Переход в состояние 2 совершается под воздействием 1 и ему соответствует выход 0, поэтому дуга из вершины 0 в 2 помечается как 1/0.
|
Рис.14.2. Граф конечного автомата
|
Переходы в состояние 3 совершаются под воздействиями 0 и 3, и им обоим соответствует выход 0, поэтому дуга из вершины 0 в 3 помечается как дизъюнкция . Аналогично определяются и другие дуги графа. Петли соответствуют переходам, при которых состояния не изменяются. Так, рассматриваемый автомат переходит из состояния 2 в 2 под воздействиями 1 и 2, которым соответствуют выходы 0 и 1. Следовательно, петля при вершине 2 помечается как дизъюнкция 1/0Ú2/1.
Матрица соединения автомата М (или матрица переходов) представляет собой квадратную таблицу, в которой номера строк и столбцов соответствуют номерам состояний. Клетка матрицы на пересечении i -й строки и j -го столбца заполняется дизъюнкцией пар «вход-выход», которая приписана дуге графа исходящей из i -й в j -ю вершину. При отсутствии такой ветви клерка заполняется нулем или остается свободной. Так для рассматриваемого примера имеем:
|
|
|
|
|
|
М =
|
| 2/0
| 1/0
| 0/0Ú3/0
|
|
| 2/0
| 1/0
| 0/1Ú3/1
|
|
|
| 1/0Ú2/1
| 0/1Ú3/1
|
|
1/0Ú2/1
| 3/1
|
| 0/0
|
|