Математический аппарат инженера

Матрица соединения автомата М (или матрица переходов) представляет собой квадратную таблицу в которой номера строк и столбцов соответствуют номерам состояний. Клетка матрицы на пересечении 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, и всех дуг, начинающихся в этих состояниях.

Пусть М₁, М₂ и M₃ - соответственно преходящий, тупиковый и изолированные подавтоматы автомата М, которые характеризуются множествами состояний S₁, S₂ и S₃. Очевидно, выделение таких подавтоматов соответствует разбиению множества S

состояний автомата М на непересекающиеся подмножества S₁, S₂ и S₃, представляющие собой классы эквивалентности ( S₁ ∪ S₂ ∪ S₃ = S и S₁ ∩ S₂ ∩ S₃ = ∅ ). Как следует из обобщенного графа (рис. 237), матрица соединения автомата может быть представлена в виде:

,

- 570 -

где μ₁₁, μ₂₂, μ₃₃ - матрицы подавтоматов М₁

, М₂ и М₃; μ₁₂ - матрица, характеризующая переходы от состояний преходящего автомата М₁ к состояниям тупикового автомата М₂. Отсюда следует, что разбиение автомата М на подавтоматы М₁, М₂ и М₃ можно осуществить преобразованием его матрицы соединений к стандартному виду путем перестановки соответствующих строк и столбцов. Например, для автомата, граф которого изображен на рис. 238, имеем:

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

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

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

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

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