Представления конечных автоматов

Типы конечных автоматов

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

Конечный автомат М определяется как система с конечным входным алфавитом, конечным выходным алфавитом, конечным множеством состояний и двумя характеристическими функциями:

;

называемыми соответственно функцией переходов и функцией выходов.

Рис.12.1. Блок-схема конечного автомата

Общая блок-схема конечного автомата (рис. 12.1) может быть представлена в виде комбинационной схемы, реализующей характеристические функции d и l, и памяти, сохраняющей на один такт предыдущее состояние автомата.

В определении автомата участвует три конечных множества X, Y, S и две функции d и l, задающие некоторые отношения между элементами этих множеств. Следовательно, конечный автомат можно обозначить упорядоченной пятеркой М = (X, Y, S, d, l). Мощности множеств X, Y, S равны соответственно:

где и - количество символов в алфавитах входной переменной X_i, выходной переменной и переменной состояния. При двоичном структурном алфавите, и. Если желают подчеркнуть мощности множеств X, Y и S, на которых определен конечный автомат, то его называют (р, q, r)- автоматом.

Характеристические функции d и l можно рассматривать как некоторые отображения множества или его подмножества соответственно на множества S и Y. Если и, автомат называется полным; если только, автомат называется полным по переходам. В случае, когда функции d и l определены не для всех наборов из множества, автомат называют неполным или частично определенным.

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

Между автоматами этих двух типов имеется взаимная связь и один из них может быть преобразован в другой.

Автомат может быть задан различными способами, например, путем словесного описания его функционирования или перечислением элементов множеств 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

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

Пример. На рис. 12.2 показан граф, построенный в соответствии с приведенной выше общей таблицей переходов. Так как из состояния 0 автомат переходит в состояния 1, 2 и 3, то из вершины 0 графа исходят дуги в вершины 1, 2 и 3. При этом переход в состояние 1 совершается под воздействием 2 и ему соответствует выход 0, поэтому дуга из вершины 0 в 1 помечается как 2/0. Переход в состояние 2 совершается под воздействием 1 и ему соответствует выход 0, поэтому дуга из вершины 0 в 2 помечается как 1/0.

Рис.12.2. Граф конечного автомата

Переходы в состояние 3 совершаются под воздействиями 0 и 3, и им обоим соответствует выход 0, поэтому дуга из вершины 0 в 3 помечается как дизъюнкция. Аналогично определяются и другие дуги графа. Петли соответствуют переходам, при которых состояния не изменяются. Так, рассматриваемый автомат переходит из состояния 2 в 2 под воздействиями 1 и 2, которым соответствуют выходы 0 и 1. Следовательно, петля при вершине 2 помечается как дизъюнкция 1/0Ú2/1.

Матрица соединения автомата М (или матрица переходов) представляет собой квадратную таблицу, в которой номера строк и столбцов соответствуют номерам состояний. Клетка матрицы на пересечении i -й строки и j -го столбца заполняется дизъюнкцией пар «вход-выход», которая приписана дуге графа исходящей из i -й в j -ю вершину. При отсутствии такой ветви клерка заполняется нулем или остается свободной. Так для рассматриваемого примера имеем: