Автомат М называется самонастраивающимся, если существует такое натуральное число щ, что для любого входного слова ап, где п>по, апеХ* любых начальных состояний Sj, steS имеетместо

v(s0,ocn)z=v(Sj,an), т.е. в самонастраивающимся автомате выходная буква у в любой такт h>no не зависит от начального состояния. Граф такого автомата для щ=3 показан на рис. 3.4.

Автомат называется автоматом без потери информации, если для любого состояния seS vl двух любых различных слов ап и сх2п:а!п, о?пеХ одинаковой длины выходные слова различны, т.е. v(s,d1 nfvisy).

Автомат M]={X],Si,Y],if/i,V]} называется подавтоматом автомата M={X,S,Y,y/,Vi}, если подавтомат имеет подмножество состояний исходного автомата и в соответствующих состояниях перерабатывает входные слова в те же слова состояний и выходные слова, что и исходный автомат, т.е. выполняется:

Рис.3.4. Граф самонастраивающегося автомата

S<SA y/1(s,x) = y/(s,x) х < X J Vj (s, x) = v(s, x)

На рис.3.5 изображен граф автоматаМ, анарис.3.6 его подавтоматМ}.

(3.7)

3.8. АНАЛИЗ КОНЕЧНЫХ АВТОМАТОВ

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

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

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

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

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

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

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

Пусть М], М2, М3 - соответственно преходящий , тупиковый и изолированный подавтоматы, составляющие автомат М, обобщенный граф которого показан на рис.3.7.

Подавтоматы Mh М2, М3 характеризуются множествами состояний Si, S2, S3. Очевидно, выделение таких подавтоматов соответствует разбиению множества S состояний автомата М на непересекающиеся подмножества S}, S2, S3 и представляющие собой классы эквивалентности (S1\JS2\JS3=S,

Sif)S2nS3=0). Как следует из обобщенного графа (см. рис.3.7), матрица соединений автомата может быть представлена в виде

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

М =

(3.8)

где jUjj - матрица подавтомата М};

состояний преходящего

/л]2 - матрица, характеризующая переход от автомата М] к состояниям тупикового автомата М2, >и22 - матрица подавтомата М2 /и33 - матрица подавтомата М3.

Отсюда следует, что разделение автомата М на подавтоматы М], М2, М3 можно осуществить преобразованием его матрицы соединений к стандартному виду путем перестановки соответствующих строк и столбцов. Эта операция достаточно легко формализуется и может быть выполнена с помощью ЭВМ.