Анализ конечных автоматов

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

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

Так, из графа на рис. 11.2 для входной последовательности (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 состояний, которое составляет тупиковый или изолированный подавтомат, М можно упростить исключением всех состояний, которые не принадлежат множеству S_i, и всех дуг, начинающихся в этих состояниях.

Пусть М ₁, М ₂ и M ₃ - соответственно преходящий, тупиковый и изолированный подавтоматы автомата М, которые характеризуются множествами состояний S ₁, S ₂ и S ₃. Очевидно, выделение таких подавтоматов соответствует разбиению множества S состоянии автомата М на непересекающиеся подмножества S ₁, S ₂ и S ₃, представляющие собой классы эквивалентности (S ₁È S ₂È S _{3 =} S и S ₁Ç S ₂Ç S _{3 =} Æ). Как следует из обобщенного графа (рис. 11.3), матрица соединения автомата может быть представлена в виде

, где - матрицы подавтоматов М 1, М 2 и M 3, - мат­рица, характеризующая переходы от состояний преходящего автомата М 1ксостояниям тупикового автомата M 2.

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

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

Пример. Для автомата, граф которого изображен на рис. 11.4, имеем:

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

Отсюда следует, что 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).

Дата добавления: 2014-01-13