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

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

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

Так, из графа на рис. 28 для входной последовательности (2, 0, 1, 1, 2, 3) и начального состояния 0 имеем выходную последовательность (0, 1, 0, 0, 1, 1) и смену состояний автомата (1, 3, О, 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₃,представляющие собой классы эквивалентности и . Как следует из обобщенного графа (рис. 29), матрица соединения автомата может быть представлена в виде:

,

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

имеем:

	3 6 2 4 7 1 5
М =	0 2/0 1/0 0	0/1 0 1/1 0 1/0 2/1	0 0 0 0
0 0 0 0 0 0	1/1 2/0 0 0/0 1/0 2/1 0/0 0 0 0/1 2/0 1/0	0 0 0 0 0 0
0 0 0 0	0 0 0 0 0 0	0/1 1/0 2/1 0/1 1/0 2/0 0

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

При реализации автоматов в двоичном структурном алфавите можно использовать рассмотренные ранее методы синтеза комбинационных схем. Но для этого необходимо закодировать состояния схемы н представить характеристические функции в виде булевых функций двоичных переменных. Такое кодирование можно осуществить преобразованием общей таблицы перехода автомата к таблице соответствия в двоичном структурном алфавите. Если элементы множеств X, У и S пронумерованы порядковыми числами, начиная с нуля, то им соответствуют коды, представляющие собой двоичные эквиваленты этих чисел. Например, для автомата, заданного в (4), таблицу переходов можно преобразовать к виду:

Заменяя десятичные числа их двоичными эквивалентами, читаемыми сверху вниз, получаем таблицу соответствия, в которой значения функций s (v + 1) и у (v) представлены двоичными кодами:

	0000 0000 1111 1111 0000 1111 0000 1111
0011 0011 0011 0011 0101 0101 0101 0101
	1111 1110 0010 1110 1111 0000 1100 1111
0110 0000 0011 0111

Отсюда видно, что комбинационная схема должна иметь четыре входа, соответствующие входным переменным x₁ (v), х₂ (v) и переменным состояния s (v), s₂ (v), а также три выхода, соответствующие переменным состояния s₁ (v + 1), s₂ (v + 1) и выходной переменной у₁ (v). Синтезировав комбинационную схему, соответствующую полученной таблице и введя два элемента задержки З₁ и З₂, получим структурную схему автомата (рис. 31).

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

Рис. 32. Граф конечного автомата (а) и его сокращенная форма (б)

Минимизация числа состоянии полных автоматов связана с отношением эквивалентности. Пусть автоматы М₁ и М₂, находящиеся соответственно в начальных состояниях, и (обозначения М₁ и М₂ могут относиться к одному и тому же автомату), под воздействием любой входной последовательности выдают одинаковые выходные последовательности, т. е. автоматы М₁ и М₂ в данных состояниях и неразличимы по внешним выходам. Такое отношение между состояниями одного и того же или двух различных автоматов обладает свойствами рефлексивности, симметричности и транзитивности, следовательно, оно является отношением эквивалентности состояний. Если состояния не эквивалентны, то их называют различимыми. Легко доказать справедливость следующих положений:

1) состояния и автомата явно различимы, если различаются соответствующие, им строки в таблице выходов;

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

Например, для автомата, граф которого изображен на рис. 32, а, общая таблица переходов имеет вид:

Из этой таблицы следует, что состояния из множества {0, 3, 4}являются явно различимыми с любым состоянием из множества {1, 2, 5, 6}. Поэтому следует искать эквивалентные состояния только среди элементов, принадлежащих одному из этих множеств. Так как строки 0 и 4 одинаковы, а строки 1 и 5 становятся одинаковыми при замене цифры в числителе 1 на 5 (или 5 на 1), то явно эквивалентными являются пары состояний {0,4} И {1,5}.

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

Первая таблица соответствует объединению пар эквивалентных состоянии {0,4} и {1, 5}, а вторая - объединению пары {2, 6}. Сокращенный автомат содержит только четыре состояния (рис.32, б).