Виталий Сигорский - Математический аппарат инженера

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

- 568 -

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

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

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

5. Анализ конечных автоматов. Полное описание поведения автомата заключается в определении последовательности выходных сигналов при возбуждении его в тактовые моменты времени некоторой последовательностью входных сигналов. Входная и выходная последовательности представляются наборами символов (или их номеров) из алфавитов Х и Y одинаковой длины l . Для такого описания, кроме характеристических функций, необходимо определить или задать начальное состояние автомата.

Наиболее удобно определять реакцию автомата на входною последовательность по его графу. Для этого достаточно проследить

- 569 -

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

Так, из графа на рис. 236 для входной последовательности (2, 0, 1, 1, 2, 3) и начального состояния 0 имеем выходную последовательность (0, 1, 0, 0, 1, 1) и смену состояний автомата (1, 3, 0, 2, 2, 3). При начальном состоянии 2 и той же входной последовательности получаем соответственно (1, 1, 0, 0, 1, 1) и (2, 3, 0, 2. 2, 3).

С помощью графа автомата легко выделить следующие характерные типы его состояний:

1) преходящее состояние, из которого можно перейти, но крайней мере, в одно другое состояние, но после этого уже нельзя возвратиться в него ни при каком воздействии (соответствующая вершина не имеет заходящих дуг, но имеет хотя бы одну исходящею дугу);

2) тупиковое состояние, в которое можно перейти, по крайней мере, из одного другого состояния, но после этого уже нельзя выйти из него ни при каком воздействии (соответствующая вершина не имеет исходящих дуг в другие вершины, но имеет хотя бы одну входящую дугу из другой вершины);

3) изолированное состояние, из которого нельзя перейти ни в какое другое состояние и в него нельзя попасть ни из какого другого состояния (соответствующая вершина содержит только петлю).

Аналогичные определения можно дать для некоторых совокупностей состояний, рассматриваемых как подавтоматы. Если начальное состояние автомата М принадлежит непустому множеству S i состояний, которое составляет тупиковый или изолированный подавтомат, то M можно упростить исключением всех состояний, которые не принадлежат множеству S i , и всех дуг, начинающихся в этих состояниях.

Пусть М 1, М 2 и M 3- соответственно преходящий, тупиковый и изолированные подавтоматы автомата М, которые характеризуются множествами состояний S 1 , S 2 и S 3 . Очевидно, выделение таких подавтоматов соответствует разбиению множества S состояний автомата М на непересекающиеся подмножества S 1 , S 2 и S 3 , представляющие собой классы эквивалентности ( S 1∪ S 2∪ S 3= S и S 1∩ S 2∩ S 3= ∅ ). Как следует из обобщенного графа (рис. 237), матрица соединения автомата может быть представлена в виде:

,

- 570 -

где μ 11, μ 22, μ 33- матрицы подавтоматов М 1, М 2 и М 3; μ 12- матрица, характеризующая переходы от состояний преходящего автомата М 1 к состояниям тупикового автомата М 2. Отсюда следует, что разбиение автомата М на подавтоматы М 1, М 2 и М 3 можно осуществить преобразованием его матрицы соединений к стандартному виду путем перестановки соответствующих строк и столбцов. Например, для автомата, граф которого изображен на рис. 238, имеем:

Рис. 237. Обобщенный граф конечного автомата.

Рис. 238. Граф конечного автомата к примеру разбиения на подавтоматы.

Отсюда следует, что S 1 = {3, 6} составляет преходящий подавтомат, S 2 = {2, 4, 7} - тупиковый подавтомат и S 3 = {1, 5} - изолированный подавтомат. Если начальное состояние принадлежит множеству S 2 , то можно упростить автомат, исключив состояния S 1∪ S 3= {3, 6, 1, 5}, а в случае принадлежности начального состояния множеству S 3 автомат упрощается исключением состояний S 1∪ S 2= {3, 6, 2, 4, 7}.

6. Синтез конечных автоматов.Реализация конечных автоматов сводится к синтезу соответствующей комбинационной схемы, преобразующей входные переменные x( ν ) и s( ν ) в выходные переменные y ( ν ) и s( ν + 1) в соответствии с заданными характеристическими функциями s( ν + 1) = δ (x( ν ), s( ν )) и y ( ν )= λ (x( ν ), s( ν )). Для сохранения состояний s( ν + 1) до следующего такта в цепь обратной связи вводится необходимое количество элементов памяти.