Размещено на http://www.allbest.ru/

Введение

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

Единый подход в описании технических и программных средств определил понятие «автомат», как математическую модель системы, обеспечивающей прием, хранение и обработку информации. Ограничение числа параметров математической модели определило новое понятие - «конечный автомат». Раздел науки, посвященный изучению таких математических моделей, называют теорией автоматов. Большинство задач теории конечных автоматов включает в себя задачи анализа поведения автомата при обработке информации и синтеза его структуры для заданного алгоритма.

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

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

Абстрактный автомат

Абстрактным автоматом называют математическую модель дискретного устройства, имеющего один входной канал, куда поступают последовательности символов какого-либо языка, один выходной канал, с которого снимают последовательности символов какого-либо другого языка и находящегося в каждый из моментов дискретного времени в каком-либо состоянии. Графически абстрактный автомат представлен рис. 1.1.

Рис. 1.1. Абстрактный автомат.

Слова входного языка можно представить символами множества X={x1, x2,… xn}, который называют входным алфавитом, а слова выходного языка - символами множества Y={y1, y2,… yp}, который называют выходным алфавитом. Множество состояний автомата Q={q1, q2,… qm} называют алфавитом состояний. С позиции формальных языков множество Q есть множество нетерминальных символов, а множества X и Y -множества терминальных символов [4].

1. Модель абстрактного автомата

Понятие "состояние" используют для того, чтобы установить функциональную зависимость генерируемых автоматом символов и / или слов выходного языка от символов и / или слов входного языка при реализации автоматом заданного алгоритма. Для каждого состояния автомата qОQ и для каждого символа xОX в момент дискретного времени [t] на выходе устройства генерируется символ yОY. Эту зависимость определяет функция выходов автомата j. Для каждого текущего состояния автомата qОQ и для каждого символа xОX в момент дискретного времени [t] автомат переходит в очередное состояние qОQ. Эту зависимость определяет функция переходов автомата y. Функционирование автомата состоит в порождении двух последовательностей: последовательности очередных состояний автомата (q1 [[1] q2 [2] q3 [3]…) и последовательности выходных символов (y1 [1] y2 [2] y3 [3]…), которые для последовательности символов (x1 [1] x2 [2] x3 [3]…) разворачиваются в моменты дискретного времени t--= 1,2,3,…. В прямоугольных скобках указывают моменты дискретного времени, которые называют иначе тактами, в круглых скобках - последовательности символов алфавитов X, Y и Q.

Итак, математическая модель конечного автомата есть трехосновная алгебра, носителями которой являются три множества X, Y и Q, а операциями - две функции j и y:--

--

M = б X; Y; Q; y;--jс, (1.1)

где X={x1; x2;… xn}	-	множество символов входного алфавита;
Y={y1; y2;… yp}	-	множество символов выходного алфавита;
Q={q1; q2;… qm}	-	множество символов состояний автомата;
y:--(QДX) ® Q	-	функция переходов автомата для отображения пары (q; x) текущего момента дискретного времени [t] в состояние q очередного момента дискретного времени [t+1];
j:--(QДX) ®--Y	-	функция выходов автомата для отображения пары (q; x) текущего момента дискретного времени [t] в символ y выходного канала этого же момента дискретного времени [t].

автомат конечный абстрактный детерминированный

Так как области определения функций переходов и выходов совпадают, то обобщенный оператор поведения автомата можно представить так:

(y;j): (QДX) ®--(QДY). (1.2)

Функционирование автомата в дискретные моменты времени t может быть описано системой рекуррентных соотношений:

(1.3)

Если на входе автомата имеем слово a = (x1x2x3…xs), то, считывая последовательно символы этого слова, на выходе автомата генерируется последовательность символов слова b по следующей схеме:

b[1]=(j(q[1]; x1 [1]));

b[2]=(j(q[1]; x1 [1])j(q[2]; x2 [2])) = (j(q[1]; x1 [1])j(q[1]; (x1 [1] x2 [2]))); (1.4)

b[s]--= (j(q[1]; x1 [1])j(q[2]; x2 [2])… j(q[s]; xs[s])) =

= (j(q[1]; x1 [1])j(q[1]; (x1 [1] x2 [2]))… j(q[1]; (x1 [1] x2 [2]… xs[s])));

Так как на каждом i-ом такте к слову длины (i-1) приписывается справа очередной символ j(q[1]; x1 [1] x2 [2]… xi[i]), то последовательность символов выходного слова можно записать так:

b--= (j(q; x1)j(q; (x1x2))…j(q; (x1x2…xs)))=(j(q;a)). (1.5)

Если считывание символов входного слова a выполняется последовательно слева направо, то всегда найдется такая последовательность (x1x2…xs-1)=g, для которой

a = ((x1x2…xs-1) xs) =(gxs), (1.6)

где g =(x1x2…xs-1) - «голова» слова a;

xs - «хвост» слова a.

Поэтому если входное слово a = (gxs), то выходное слово b можно записать так:

b--= j(q;a) = j(y(q;g); xs). (1.7)

Это означает, что последний символ слова b есть результат работы автомата, начавшего работу в состоянии q и считавшего последний символ слова a, но значение этого символа зависит от всей входной последовательности.

Длина выходного слова всегда равна длине входного слова.

Изменение состояний автомата для последовательности символов слова a = (x1x2x3…xs) может быть описано следующей схемой:

q[2] = y(q[1]; x1 [1]);

q[3] = y(q[2]; x2 [2]) = y(y(q[1]; (x1 [1]); x2 [2])); (1.8)

q [s+1] = y(q[s]; xs[s]) = y(y… (y(y(y(q[1]; x1 [1]); x2 [2]); x3 [3]);… xs-1 [s-1]); xs[s]),

где q[1] - начальное состояние автомата.

Так как за один такт автомат считывает один символ входного слова, то в последовательности состояний автомата можно не указывать номер такта, то есть.

q [s+1] = y(y… (y(y(y(q; x1); x2); x3)… xs-1); xs). (1.9)

Если входное слово a = (gxs), то изменение состояния автомата может быть описано так:

q [s+1] = y(y(q;g); xs). (1.10)

Это означает, что q [s+1] есть последнее состояние автомата, начавшего работу в состоянии q и считавшего последний символ слова a в момент дискретного времени s.

Функциональная схема абстрактного автомата представлена на рис. 1.2.

Рис. 1.2 Функциональная схема абстрактного автомата.

Если функции переходов и выходов однозначно определены для каждой пары (q; x)О(QДX), тоавтомат называют детерминированным. В противном случае автомат называют недетерминированным или частично определенным.

Если функция переходов и / или функция выходов являются случайными, то автомат называют вероятностным.

Если у автомата задано начальное состояние q=q0ОQ, в котором он находится всегда до приема первого символа входного слова, то автомат называют инициальным. В этом случае модель автомата записывают так:

M = б X; Y; Q;y;j; q0с, (1.11)

Последовательность символов в слове b и последовательность состояний автомата q однозначно определяются начальным состоянием автомата q=q0 и последовательностью символов во входном канале a. Поэтому отображение входного слова a--на выходное слово b--чаще называют автоматным отображением, то есть b--= М (q0;a), а М - автоматным оператором.

Автоматное отображение обладает свойствами:

входное и выходное слова имеют одинаковую длину (свойство сохранения длины);

2) yi-ый символ выходного слова зависит от всей последовательности символов входного слова, до xi-го включительно; кроме того если a=a1a2,--то------b=b1b2..

2. Типы конечных автоматов

По способу формирования функций выхода выделяют автоматы Мили и Мура.

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

(1.12)

(1.13)

Особенностью автомата Мили является то, что функция выходов является двухаргументной и символ в выходном канале y[t] обнаруживается только при наличии символа во входном канале x[t]. Функциональная схема не отличается от схемы абстрактного автомата (см. рис 1.2 и 1.3).



Рис. 1.3. Функциональная схема автомата Мили

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

(1.14)

(1.15)

Особенностью автомата Мура является то, что символ y[t] в выходном канале существует все время пока автомат находится в состоянии q[t]. Функциональная схема автомата Мура представлена на рис. 1.4.

Рис. 1.4. Функциональная схема автомата Мура

Объединение автоматов Мили и Мура представляет С-автомат, для которого схема рекуррентных соотношений имеет вид:

 (1.16)

Потребность такого автомата возникает при формировании автоматных сетей (см. 2).

Функциональная схема С-автомата представлена на рис. 1. 5.

Рис. 1. 5. Функциональная схема С-автомата

Интересно выделить особые классы автоматов, математические модели которых опираются только на два носителя алгебры.

Пусть X=Ж. Тогда математическая модель и система рекуррентных соотношений имеют вид:

(1.17)

(1.18)

Функциональная схема автомата приведена на рис. 1.6.

Рис. 1.6. Функциональная схема порождающего автомата

Особенностью функционирования такого автомата является генерация последовательности символов выходного слова только в зависимости от последовательности состояний автомата. Такие автоматы называют порождающими или автономными. С помощью такого автомата генерируется последовательность управляющих команд на какие-либо объекты внешней среды.

Пусть Y=Ж. Тогда математическая модель и система рекуррентных соотношений имеют вид:

(1.19)

q[t+1] = y(q[t]; x[t]); (1.20)

Особенностью функционирования такого автомата является распознавание в последовательности изменений аргумента функции переходов значения (qi[t]; xi[t]) и перевод автомата в заключительное состояние qk. С помощью такого автомата обнаруживают заданные возмущения со стороны объектов внешней среды или распознают заданную последовательность входных символов. Поэтому такие автоматы называют распознающими. Часто и автомат Мура представляют автоматом без выхода, так как его выходной сигнал эквивалентен состоянию автомата.

Пусть Q=Ж. Тогда математическая модель и система рекуррентных соотношений имеют вид:

(1.21)

y[t] = j(x[t]); (1.22)

Функциональная схема автомата приведена на рис. 8.



Рис. 1.8. Функциональная схема комбинационного автомата

Особенностью функционирования такого автомата является отсутствие «памяти», т.е. на каждый символ входного алфавита автомат генерирует символ выходного алфавита без учета состояния автомата. Такие автоматы чаще всего называют комбинационными автоматами.

3. Описание автомата

Автоматы удобно описывать с помощью таблиц, а для наглядности использовать графы. При табличном описании задают две таблицы, одна из которых раскрывает функцию переходов y:--(QДX)®--Q, а другая - функцию выходов j:--(QДX)®--Y. Число строк таблиц m равно числу состояний автомата, т.е. m = кQ к. Число столбцов таблиц n равно числу символов входного алфавита, т.е. n = кX к. В позиции первой таблицы записывают значения очередных состояний автомата q[t+1]ОQ, в которые он переходит для каждой пары (q[t]; x[t])О(QДX). В позиции второй таблицы записывают значения символов выходного алфавита y[t]ОY, которые генерирует автомат для каждой пары (q[t]; x[t])О(QДX). Если в таблицах 1 и 2 определены значения q[t+1]ОQ и y[t]ОY для каждой пары (q[t]; x[t])О(QДX), то есть заполнены все позиции таблиц, то дано описание детерминированного автомата.

Обычно эти таблицы совмещают в одну, которая раскрывает оператор поведения (y;j): (QДX) ®--(QДY). В позициях этой таблицы записывают пары (q[t+1]; y[t]) для каждой пары (q[t]; x[t]).

Таблицы абстрактного автомата совпадают с таблицами автомата Мили. Поэтому таблица 1.3 описывает поведение автомата Мили. Таблица автомата Мура (см. таблицу 1.4) несколько отличается от таблицы автомата Мили, так как j:Q®Y. Значение выходного символа приписывают, как метку, состоянию автомата. Описание С-автомата есть объединение таблиц 1.3 и 1.4. Так как в таблицах 1.3 и 1.4 определены все позиции, то такими таблицами дано описание детерминированных автоматов.

В практике проектирования автоматов встречаются случаи, когда функции переходов и / или выходов не определены для некоторых значений символов входного алфавита. В этом случае говорят, что автомат недетерминированный или частично определенный. При описании таких автоматов неопределенные позиции таблиц помечаются символом «*». Например, в таблицах 1.5, 1.6, 1.7 и 1.8 приведено описание недетерминированных автоматов.

Поведение автомата удобно анализировать с помощью графов, вершинами которого являются элементы множества qОQ. Тогда вершина-исток есть образ текущего состояния q[t], а вершина-сток - образ очередного состояния q[t+1]. Дуги отображают переход автомата из одного состояния в другое (q[t]; q[t+1]) под воздействием x[t]ОX. Для описания автомата с помощью графов удобно воспользоваться таблицами соединений состояний автомата. Строки и столбцы такой таблицы представляют символы qОQ. Следовательно, число строк и столбцов таблицы равно m. Строки этой таблицы характеризуют текущее состояние, т.е. q[t], а столбцы - очередное, т.е. q[t+1]. Позиции таблицы заполняют значениями пары (x[t]/y[t]) для соответствующего перехода автомата из текущего состояния в очередное.

При начертании графа детерминированного автомата следует соблюдать следующие условия: 1) для каждого символа xОX есть дуга, исходящая из вершины qОQ; 2) каждый символ xОX у каждой вершины-истока qОQ принадлежит только одной дуге; 3) если между двумя вершинами qОQ существует несколько дуг, что может быть обусловлено переходом автомата из состояния qsОQ в состояние qtОQ при различных символах на входе, то есть xi xj, то эти дуги могут быть заменены одной дугой с указанием дизъюнктивной связи этих состояний (например, если yuyv, то на дуге следует указать (xi/yuЪxj/yv);.если yu=yv=y, то - (xiЪxj)/y).

Таблица 1.11. Детерминированный автомат Мили (y;j): (QДX) ®--(QДY)

Текущее состояние qОQ	Символы входного алфавита xiОX
	x1	x2	x3	x4
q1	q2; y1	q3; y1	q4; y1	q1; y3
q2	q3; y3	q4; y1	q1; y2	q2; y2
q3	q2; y1	q3; y2	q1; y1	q2; y3
q4	q4; y2	q1; y1	q2; y2	q1; y1

Составить таблицу соединения состояний автомата и начертить граф. Найти генерируемые автоматом слова b--для различных начальных состояний,--если на входе автомата задано слово a = (x1x2x3x4x4x3x2x1).

Для формирования таблицы соединения состояний автомата находим по таблице 1.11 число строк и столбцов. Это число равно 4. Имена строк и столбцов заданы именами элементов множества qОQ. В позициях таблицы будут значения (x/y), соответствующие переходу из состояния q[t] в состояние q[t+1]. Следует обратить внимание, что переход из состояния q3 в q2 обусловлен двумя входными символами (x1 и x4), а для каждой пары (q3; x1) и (q3; x4) автомат генерирует в выходном канале особый символ (y1 и y3). Поэтому на дуге (q3; q2) следует указать (x1/y1Ъx4/y3). Переход из состояния q4 в q1 обусловлен также двумя входными символами (x2 и x4), но автомат генерирует только один символ на выходе y1. Поэтому на дуге (q4; q1) следует указать (x2Ъx4)/y1. Остальные переходы автомата обусловлены появлением только одного входного символа. Таблица 1.12 представляет таблицу соединений состояний автомата Мили, а рис. 9 - его граф.

Таблица 1.12. Соединение состояний автомата Мили (y;j): (QДX) ®--(QДY)

текущее состояние qОQ	очередное состояние qОQ
	q1	q2	q3	q4
q1	x4/y3	x1/y1	x2/y1	x3/y1
q2	x3/y2	x4/y2	x1/y3	x2/y1
q3	x3/y1	(x1/y1)Ъ(x4/y3)	x2/y2	-
q4	(x2Ъx4)/y1	x3/y2	-	x1/y2

Рис. 1.9. Граф детерминированного автомата Мили

Для поиска слов b при различных начальных условиях необходимо проследить всю последовательность изменения состояний автомата для каждого очередного символа слова a:

пусть q1=q0, тогда

a[t]: x1 [1] x2 [2] x3 [3] x4 [4] x4 [5] x3 [6] x2 [7] x1 [8]

q[t+1]: q1 [1] q2 [2] q4 [3] q2 [4] q2 [5] q2 [6] q1 [7] q3 [8] q2 [9]

b[t]: y1 [1] y1 [2] y2 [3] y2 [4] y2 [5] y2 [6] y1 [7] y1 [8],

то есть b=(y1y1y2y2y2y2y1y1);

пусть q2=q0, тогда

a[t]: x1 [1] x2 [2] x3 [3] x4 [4] x4 [5] x3 [6] x2 [7] x1 [8]

q[t+1]: q2 [1] q3 [2] q3 [3] q1 [4] q1 [5] q1 [6] q4 [7] q1 [8] q2 [9]

b[t]: y3 [1] y2 [2] y1 [3] y3 [4] y3 [5] y1 [6] y1 [7] y1 [8],

то есть b=(y3y2y1y3y3y1y1y1);

пусть q3=q0, тогда

a[t]: x1 [1] x2 [2] x3 [3] x4 [4] x4 [5] x3 [6] x2 [7] x1 [8]

q[t+1]: q3 [1] q2 [2] q4 [3] q2 [4] q2 [5] q2 [6] q1 [7] q3 [8] q2 [9]

b[t]: y1 [1] y1 [2] y2 [3] y2 [4] y2 [5] y2 [6] y1 [7] y1 [8],

то есть b=(y1y1y2y2y2y2y1y1);

пусть q4=q0, тогда

a[t]: x1 [1] x2 [2] x3 [3] x4 [4] x4 [5] x3 [6] x2 [7] x1 [8]

q[t+1]: q4 [1] q4 [2] q1 [3] q4 [4] q1 [5] q1 [6] q4 [7] q1 [8] q2 [9]

b[t]: y2 [1] y1 [2] y1 [3] y1 [4] y3 [5] y1 [6] y1 [7] y1 [8],

то есть b=(y2y1y1y1y3y1y1y1).

Анализ показывает, что при различных начальных состояниях реакция автомата на одинаковые слова различна. Это подтверждает необходимость указания начального состояния qi=q0. Только в этом случае каждому слову на входе автомата найдется единственный образ на выходе.

Пример 1.2. Детерминированный автомат Мура задан таблицей поведения (см. таблицу 13).

Таблица 1.13. Детерминированный автомат Мура y:--(QДX)®--Q; j:--Q®Y

текущее состояние qОQ	символы входного алфавита xОX	выход yОY
	x1	x2	x3	xn
q1	q2	q3	q4	q1	y1
q2	q3	q4	q1	q2	y3
q3	q2	q3	q1	q2	y2
qm	q4	q1	q2	q1	y1

Составить таблицу соединения состояний автомата и начертить граф. Найти генерируемые автоматом слова b--для различных начальных состояний,--если на входе автомата задано слово a = (x1x2x3x4x4x3x2x1).

Для формирования таблицы соединения состояний автомата находим по таблице 1.13 число строк и столбцов. Это число равно 4. Имена строк и столбцов заданы именами элементов множества qОQ. Элементами таблицы соединения состояний автомата будут значения x, соответствующие переходу из состояния q[t] в состояние q[t+1]. Переход из состояния q3 в q2 обусловлен двумя входными символами (x1 и x4). Поэтому на дуге (q3; q2) cледует указать (x1Ъx4). Переход из состояния q4 в q1 обусловлен также двумя входными символами (x2 и x4). Поэтому на дуге (q4; q1) cледует указать (x2Ъx4). Таблица 1.14 представляет таблицу соединений состояний автомата Мура, а рис. 1.10 - его граф.

Tаблица 1.14 Соединение состояний автомата Мура y:--(QДX)®--Q; j:--Q®Y

текущее состояние qОQ	очередное состояние qОQ	выход yОY
	q1	q2	q3	q4
q1	x4	x1	x2	x3	y1
q2	x3	x4	x1	x2	y3
q3	x3	(x1Ъx4)	x2	-	y2
q4	(x2Ъx4)	x3	-	x1	y1

Рис. 1.10 Граф детерминированного автомата Мура

Для поиска слов b при различных начальных условиях необходимо проследить всю последовательность изменения состояний автомата для каждого очередного символа слова a:

пусть q1=q0, тогда

a[t]: x1 [1] x2 [2] x3 [3] x4 [4] x4 [5] x3 [6] x2 [7] x1 [8]

q[t+1]: q1 [1] q2 [2] q4 [3] q2 [4] q2 [5] q2 [6] q1 [7] q3 [8] q2 [9]

b[t]: y1 [1] y3 [2] y1 [3] y3 [4] y3 [5] y3 [6] y1 [7] y2 [8],

то есть b=(y1y3y1y3y3y3y1y2);

пусть q2=q0, тогда

a[t]: x1 [1] x2 [2] x3 [3] x4 [4] x4 [5] x3 [6] x2 [7] x1 [8]

q[t+1]: q2 [1] q3 [2] q3 [3] q1 [4] q1 [5] q1 [6] q4 [7] q1 [8] q2 [9]

b[t]: y3 [1] y2 [2] y2 [3] y1 [4] y1 [5] y1 [6] y1 [7] y1 [8],

то есть b=(y3y2y2y1y1y1y1y1);

пусть q3=q0, тогда

a[t]: x1 [1] x2 [2] x3 [3] x4 [4] x4 [5] x3 [6] x2 [7] x1 [8]

q[t+1]: q3 [1] q2 [2] q4 [3] q2 [4] q2 [5] q2 [6] q1 [7] q3 [8] q2 [9]

b[t]: y2 [1] y3 [2] y1 [3] y3 [4] y3 [5] y3 [6] y1 [7] y2 [8],

то есть b=(y2y3y1y3y3y3y1y2);

пусть q4=q0, тогда

a[t]: x1 [1] x2 [2] x3 [3] x4 [4] x4 [5] x3 [6] x2 [7] x1 [8]

q[t+1]: q4 [1] q4 [2] q1 [3] q4 [4] q1 [5] q1 [6] q4 [7] q1 [8] q2 [9]

b[t]: y1 [1] y1 [2] y1 [3] y1 [4] y1 [5] y1 [6] y1 [7] y1 [8]

то есть b=(y1y1y1y1y1y1y1y1).

Этот пример также подтверждает необходимость указания начального состояния q=q0.

Пример 1.3. Недетерминированный автомат Мили задан таблицей поведения (см. таблицу 1.15).

Составить таблицу соединения состояний автомата и начертить граф. Найти генерируемые автоматом слова b--для различных a и различных начальных состояний.

Элементами таблицы соединения состояний автомата будут значения (x/y), соответствующие переходу из состояния q[t] в состояние q[t+1]. Следует обратить внимание, что не определены переходы из состояния q2 для входного символа x1, из состояния q3 для входного символа x2 и из состояния q4 для входного символа x4.

Не определены также значения символов на выходе для состояния q1 и входного символа x2, для состояния q2 и входного символа x4 и для состояния q3 и входного символа x2. Таблица 1.16 представляет таблицу соединений состояний недетерминированного автомата Мили, а рис. 11 - его граф.

Таблица 1.15. Недетерминированный автомат Мили (y;j): (QДX) ®--(QДY)

текущее состояние qОQ	символы входного алфавита xiО--X
	x1	x2	x3	x4
q1	q2; y1	q3;*	q4; y1	q1; y3
q2	*; y3	q4; y1	q1; y2	q2;*
q3	q2; y1	*;*	q1; y1	q2; y3
q4	q4; y2	q1; y1	q2; y2	*; y1

Таблица 1.16. Соединение состояний автомата Мили (y;j): (QДX) ®--(QДY)

текущее состояние qОQ	очередное состояние qОQ
	q1	q2	q3	q4
q1	x4/y3	x1/y1	x2/*	x3/y1
q2	x3/y2	x4/*	-	x2/y1
q3	x3/y1	(x1/y1)Ъ(x4/y3)	-	-
q4	x2/y1	x3/y2	-	x1/y2

Для поиска слов b, генерируемых недетерминированным автоматом Мура также необходимо проследить последовательность изменения состояний автомата для каждого очередного символа слова a:

пусть q1=q0 и a= (x1x2x3x3x3x2x4x4), тогда

a[t]: x1 [1] x2 [2] x3 [3] x3 [4] x3 [5] x2 [6] x4 [7] x4 [8]

q[t+1]: q1 [1] q2 [2] q4 [3] q2 [4] q1 [5] q4 [6] q1 [7] q1 [8] q1 [9]

b[t]: y1 [1] y1 [2] y2 [3] y2 [4] y1 [5] y1 [6] y3 [7] y3 [8],

то есть b=(y1y1y2y2y1y1y3y3);

Рис. 1.11 Граф недетерминированного автомата Мили

пусть q1=q0 и a= (x2x2x3x4x4x3x2x1), тогда

a[t]:x2 [1] x2 [2] x3 [3] …

q[t+1]:q1 [1] q3 [2] * …

--b[t]:*[1] *[2] …,

то есть b=--(* * … и автомат «зависает» на третьем символе слова a;

пусть q1=q0 и a= (x2x2x3x4x4x3x2x1), тогда

a[t]: x1 [1] x4 [2] x3 [3] x2 [4] x3 [5] x2 [6] x4 [7] x4 [8]

q[t+1]: q1 [1] q2 [2] q2 [3] q1 [4] q3 [5] q1 [6] q3 [7] q2 [8] q2 [9]

b[t]: y1 [1] *[2] y2 [3] * [4] y1 [5] * [6] y3 [7] * [8],

то есть b=(y1*y2*y*y*) содержит четыре символа «*»;

пусть q2=q0 и a= (x1x4x3x2x3x2x4x4), тогда

a[t]: x1 [1] x4 [2] …

q[t+1]: q2 [1] *. [2] …

b[t]: y3 [1] …

то есть b=--(y3 … и автомат «зависает» на втором символе слова a.

Анализ показывает, что недетерминированный автомат Мили может

1) генерировать на выходе последовательности символов, равные последовательностям символов на входе, но содержащие неопределенные символы «*», что разрушает образ слова a;

2) «зависать» в состоянии, для которого не определен переход в очередное состояние.

Пример 1.4. Недетерминированный автомат Мура задан таблицей поведения (см. таблицу 1.17).

Таблица 1.17. Недетерминированный автомат Мура y:--(QДX)®--Q; j:--Q®Y

текущее состояние qОQ	символы входного алфавита xОX	выход yОY
	x1	x2	x3	xn
q1	q2	q3	q4	q1	y1
q2	*	q4	q1	q2	*
q3	q2	*	q1	q2	y2
qm	q4	q1	q2	*	y1

Составить таблицу соединения состояний автомата и начертить граф. Найти генерируемые автоматом слова b--для различных a и различных начальных состояний.

Элементами таблицы соединения состояний автомата будут значения x, соответствующие переходу из состояния q[t] в состояние q[t+1]. Следует обратить внимание, что не определены переходы из состояния q2 для входного символа x1, из состояния q3 для входного символа x2 и из состояния q4 для входного символа x4. Не определено также значение символа на выходе для состояния q2. Таблица 1.18 представляет таблицу соединений состояний недетерминированного автомата Мура, а рис. 1.12 - его граф.

Таблица 1.18. Соединение состояний автомата Мура y:--(QДX)®--Q; j:--Q®Y

текущее состояние qОQ	очередное состояние qОQ	выход yОY
	q1	q2	q3	q4
q1	x4	x1	x2	x3	y1
q2	x3	x4	*	x2	*
q3	x3	(x1Ъx4)	*	-	y2
q4	x2	x3	-	x1	y1

Рис. 1.12. Граф недетерминированного автомата Мура

Для поиска слов b при различных начальных условиях необходимо проследить всю последовательность изменения состояний автомата для каждого очередного символа слова a:

пусть q1=q0 и a= (x2x3x2x3x3x1x2x4), тогда

a[t]: x2 [1] x3 [2] x2 [3] x3 [4] x3 [5] x1 [6] x2 [7] x4 [8]

q[t+1]: q1 [1] q3 [2] q1 [3] q3 [4] q1 [5] q4 [6] q4 [7] q1 [8] q1 [9]

b[t]: y1 [1] y2 [2] y1 [3] y2 [4] y1 [5] y1 [6] y1 [7] y1 [8],

то есть b=--(y1y2y1y2y1y1y1y1);

пусть q2=q0 и a= (x2x3x1x4x4x3x2x1), тогда

a[t]: x2 [1] x3 [2] x1 [3] x4 [4] …

q[t+1]: q2 [1] q4 [2] q2 [3] * [4] …

b[t]: * [1] y1 [2] * [3] …,

то есть b=--(*y1* … и автомат «зависает» на четвертом символе слова a;

пусть q1=q0 и a= (x1x2x3x3x1x3x1x3), тогда

a[t]: x1 [1] x2 [2] x3 [3] x3 [4] x1 [5] x3 [6] x1 [7] x3 [8]

q[t+1]: q1 [1] q2 [2] q4 [3] q2 [4] q1 [5] q2 [6] q1 [7] q2 [8] q1 [9]

b[t]: y1 [1] *[2] y1 [3] * [4] y1 [5] * [6] y1 [7] * [8],

то есть b=(y1*y1*y1*y1*) содержит четыре символа про»*»;

пусть q2=q0 и a= (x1x4x3x2x3x2x4x4), тогда

a[t]: x1 [1] x4 [2] …

q[t+1]: q2 [1] * [2] …

b[t]: * …,

то есть b=--(* … и автомат «зависает» на втором символе слова a.

Анализ показывает, что для недетерминированного автомата Мура характерны такие же недостатки, как для недетерминированного автомата Мили.

Эквивалентность автоматов

Эквивалентность автоматов определяют по их одинаковой реакции на входные последовательности символов, то есть по формированию одинаковых выходных последовательностей символов.

Так как модель автомата представляет трехосновную алгебру, то для сравнения двух автоматов необходимо найти три оператора, формирующих отображение множеств X, Q и Y модели одного автомата на соответствующие множества модели другого автомата. После этого необходимо оценить влияние этих операторов на исполнение функций переходов и выходов каждым автоматом. Если на одинаковые последовательности входных символов автоматы генерируют одинаковые последовательности выходных символов, то такие автоматы эквивалентны.

Рассмотрим модели двух абстрактных автоматов:

(1.23)

Пусть даны операторы:

(1.24)

Если при исполнении функций переходов и выходов выполняются условия:

 (1.25)

то совокупность операторов q=(f; g; h)--формирует гомоморфное отображение модели автомата М1 на модель автомата М2 когда каждому значению x1kОX1, y1jОY1 и q1iОQ1 соответствуют единственные образы x2kОX2,--y2jОY2,--q2iОQ1.

Пусть даны операторы:

(1.26)

Если при исполнении функций переходов и выходов выполняются условия:

(1.27)

то совокупность операторов q-1--=--бf-1; g-1; h-1с определяет гомоморфное отображение модели автомата М2 на модель автомата М1 когда каждому значению x2kОX2, y2jОY и q2iОQ2 соответствуют единственные образы x1kОX1, y1jОY1, q1iОQ1.

Если найдена совокупность операторов (q;q-1), для которой

q°q-1= q-1°q =1, (1.28)

то такое взаимное отображение называют изоморфным.

Изоморфное отображение рефлексивно, симметрично и транзитивно. Особый интерес для оценки эквивалентности автоматов представляет случай, когда f=1. По условиям (1.25) и (1.27) для xkОX имеем:

(1.29)

Если существуют такие q1i и q2i, для которых значения функций выходов j1 (q1i; xk) и j2 (q2i; xk) совпадают для всех xkОX, то есть

j1 (q1i; xk)=j2 (q2i; xk), (1.30)

то g=g-1=1, h(q1i)=q2i, h-1 (q2i)=q1i. При этом Y1=Y2=Y. Такие состояния q1i и q2i называют неотличимыми по выходам автоматов.

В результате просмотра множества пар неотличимых состояний (q1i; q2i)О(Q1ДQ2) можно найти несколько подмножеств, которые формируют разбиение множества (Q1ДQ2) на классы неотличимых по выходу состояний.

Если для пары неотличимых состояний (q1i; q2i) значения функций переходов формируют для всех символов xkОX также пары неотличимых состояний (y(q1i[t]; xk[t]);y(q2i[t]; xk[t])), то состояния q1i и q2i называют совместимыми. В результате такого просмотра всех пар одного класса неотличимых состояний формируется его разбиение на классы совместимых состояний.

Состояния q1i и q2i являются эквивалентными, если для всякой входной последовательности a=(x1x2…xn) выполняется условие:

М1 (q1i;a)=М2 (q2i;a), (1.31)

Поэтому необходимо проследить изменения значений функций переходов (y(q1i[t]; xk[t]);y(q2i[t]; xk[t])) для каждого символа входной последовательности a=(x1x2…xn).

Множество всех пар (q1i; q2i), для которых выполняется условие (1.31), формирует класс эквивалентных состояний.

Если входной и выходной алфавиты у двух автоматов совпадают, то автомат M2 покрывает автомат M1, если j2 (h(q1i);a)=j1 (q1i;a) для всех aОXn, а автомат M1 покрывает автомат M2, если входной и выходной алфавиты у этих автоматов общие и j1 (h-1 (q2i);a)=j2 (q2i;a) для всех aОXn.

По условиям изоморфизма автоматы M1 и M2 эквивалентны, если M1 покрывает M2 и M2 покрывает M1. У эквивалентных автоматов существуют эквивалентные состояния q1i и q2i.

Если для эквивалентных автоматов М1 и М2 имеем чQ1ч < чQ2ч, то автомат М1, имеющий меньшее число состояний m1 = чQ1ч, покрывает автомат М2, имеющий большее число состояний m2 = чQ2ч. Автомат, который нельзя покрыть автоматом с меньшим числом состояний, называют минимальным.

Для поиска эквивалентных состояний q1i и q2i удобно использовать таблицы переходов пар состояний двух автоматов. В каждой паре левый элемент есть состояние автомата М1, а правый элемент - состояние автомата М2. Левый столбец такой таблицы предназначен для указания неотличимых пар состояний, которые формируются по таблицам выходов автоматов следующим правилом: «если среди множества состояний двух автоматов Q1 и Q2 найдется такая пара (q1; q2), у которой значения функций выходов равны для каждого символа входного алфавита xkОX, т.е. j1 (q1i; xk)=j2 (q2i; xk), то состояния q1 и q2 неотличимы;»

Позициями таблицы являются пары состояний двух автоматов, в которые они переходят из соответствующих состояний пары неотличимых состояний при подаче на входы автоматов символа xk. Значения очередных состояний могут быть найдены по таблицам переходов автоматов М1 и М2 для соответствующего символа xkОX, т.е. (q1=y(q1i; xk); q2 = y(q2i; xk)).

Пусть таблица переходов пар состояний двух автоматов представлена таблицей 1.19, где пары неотличимых состояний, приведенные в левом столбце, есть (q1i; q2j), (q1j; q2p), (q1p; q2s), (qs; q2i).

Таблица 1.19.

текущая пара неотличимых состояний (q1; q2)	символы входного алфавита xiОX
	x1	x2	…	xn
…	…	…	…	…
(q1i; q2j)	(q1i; q2j)	(q1j; q2p)	…	(q1s; q2i)
(q1j; q2p)	(q1i; q2j)	(q1p; q2p)	…	(q1s; q2i)
(q1p; q2s)	(q1j; q2p)	(q1j; q2p)	…	(q1j; q2p)
(q1s; q2i)	(q1s; q2p)	(q1p; q2j)	…	(q1j; q2i)
…	…	…	…	…

Анализ таблицы показывает, что

1) состояния q1i и q2j совместимы, т.к. при приеме каждого символа входного алфавита неотличимые состояния автоматов М1 и М2 переходят в в пары также неотличимых состояний;

2) состояния q1p и q2s совместимы, т.к. при приеме каждого символа входного алфавита неотличимые состояния автоматов М1 и М2 остаются в одной паре неотличимых состояний;

3) состояния q1j и q2p несовместимы, т.к. при приеме символа x2 неотличимые состояния автоматов М1 и М2 переходят в различные пары неотличимых состояний;

4) состояния q1s и q2i несовместимы, т.к. при приеме каждого символа входного алфавита неотличимые состояния автоматов М1 и М2 переходят в различные пары неотличимых состояний.

Следовательно, автоматы М1 и М2, даже при наличии совместимых состояний, не эквивалентны между собой.

Пример 1.5. Пусть даны автомат M1=бX1; Y1; Q1;y1;j1с,--где X1={0; 1}, Y1={0; 1}, Q1={q11; q12; q13}, y1 и j1 (см. таблицу 1.20) и автомат M2=бX2; Y2; Q2;y2;j2с,--где----X2={0; 1}, --Y2={0; 1}, Q2={q21; q22}, y2 и--j2.

Граф автомата М1 приведен на рис. 1.13, автомата М2 - на рис. 1.14. Определить эквивалентность автоматов М1 и М2.

Рис. 1.13 Граф автомата М1 Рис. 1.14 Граф автомата М2

Для автоматов М1 и М2 неотличимыми по выходу являются пары состояний (q11; q21), (q12; q22) и (q13; q21). При этом формируются два класса неотличимых состояний {(q11; q21); (q13; q21)} и {(q12; q22)}.

Если для неотличимой пары (q11; q21) при входном символе «0» автоматы М1 и М2 переходят в неотличимую пару состояний (q13; q21), а при входном символе «1» - в неотличимую пару (q12; q22), то состояние q11 автомата М1 и состояние q21 автомата М2 являются совместимыми.

Если для неотличимой пары состояний (q12; q22) при входном символе «0» автоматы М1 и М2 переходят в неотличимую пару состояний (q11; q21), а при входном символе «1» - в неотличимую пару (q13; q21), то состояние q12 автомата М1 и состояние q22 автомата М2 также являются совместимыми.

И наконец, если для неотличимой пары состояний (q13; q21) при входном символе «0» автоматы М1 и М2 переходят в неотличимую пару состояний (q11; q21), а при входном символе «1» - в неотличимую пару (q12; q22), то состояние q13 автомата М1 и состояние q21 автомата М2 являются совместимыми.

Если состояние q13 автомата М1 совместимо с состоянием q21 автомата М2, а состояние q21 автомата М2 совместимо с состоянием q11 автомата М1, то согласно свойству транзитивности состояние q11 автомата М1 совместимо с состоянием q13 автомата М1.

Проверку эквивалентности автоматов можно выполнить, обрабатывая одинаковые последовательности символов каждым автоматом и анализируя последовательности символов на их выходах.

Пусть для автомата М1 имеем q11=q0 и a = (01010101). Тогда процесс обработки входного слова формирует следующие последовательности:

вход: 0 [1] 1 [2] 0 [3] 1 [4] 0 [5] 1 [6] 0 [7] 1 [8];

q: q11 [1] q13 [2] q12 [3] q11 [4] q12 [5] q11 [6] q12 [7] q13 [8] q12 [9];

выход: 0 [1] 1 [2] 1 [3] 1 [4] 1 [5] 1 [6] 1 [7] 1 [8],

то есть b1= (01111111).

Пусть для автомата М2 имеем q21=q0 и a=(01010101). Тогда процесс обработки входного слова формирует следующие последовательности:

вход: 0 [1] 1 [2] 0 [3] 1 [4] 0 [5] 1 [6] 0 [7] 1 [8];

q: q21 [1] q21 [2] q22 [3] q21 [4] q22 [5] q21 [6] q22 [7] q21 [8] q22 [9];

выход: 0 [1] 1 [2] 1 [3] 1 [4] 1 [5] 1 [6] 1 [7] 1 [8],

то есть b2= (01111111).

Итак, автоматы М1 и М2 эквивалентны. Так как автомат М2 имеет меньшее число внутренних состояний, то он покрывает автомат М1.

Эквивалентность состояний детерминированного автомата

Особый интерес представляет анализ множества состояний одного автомата. Если у автомата М есть состояния qi и qj, для которых значения функций выходов j(qi; xk) и j(qj; xk) совпадают для всех символов множества X, то есть

j(qi; xk) = j(qj; xk), (1.32)

то состояния qi и qj автомата М формируют неотличимую пару (qi; qj)О(QДQ).

Множество неотличимых пар (qi; qj)О(QДQ), имеющих одинаковые значения функций выходов для каждого символа xkОX формирует класс неотличимых состояний Q'i. Если множество неотличимых пар содержит пары (qi; qj), (qj; qk) и (qi; qk), то есть выполняется условие транзитивности для отношения неотличимости, то класс неотличимых состояний формирует множество Q'i={qi; qj; qk}.

Если для неотличимой пары состояний (qi; qj) значения функций переходов формируют для всех символов xkОX также пары неотличимых состояний (y(qi[t]; xk[t]);y(qj[t]; xk[t])), то такие состояния qi и qj называют совместимыми.

Множество совместимых пар, имеющих одинаковые значения функций переходов для каждого символа xkОX, формирует класс совместимых состояний Q''i. Если множество совместимых пар содержит пары (qi; qj), (qj; qk) и (qi; qk), то есть выполняется условие транзитивности для отношения совместимости, то класс совместимых состояний есть Q''i={qi; qj; qk}.

Если состояния qi и qj автомата М неотличимы и совместимы, то они эквивалентны. Поэтому класс совместимых состояний есть класс эквивалентных состояний.

Для поиска эквивалентных состояний автомата М также следует заполнить таблицу переходов пар неотличимых состояний. Левый столбец таблицы предназначен для указания пар неотличимых состояний (qi; qj)О(QДQ), которые определяют по таблице выходов для всех xkОX по условию j(qi; xk)=j(qj; xk). Позициями этой таблицы являются пары (y(qi; xk);y(qj; xk)), в которые переходит автомат из неотличимой пары (qi; qj) для каждого символа xkОX. Значения (y(qi; xk);y(qj; xk)) определяются по таблице переходов автомата М.

Пусть таблица переходов пар состояний одного автомата представлена таблицей 1.22, где множество пар неотличимых состояний есть (qp; qr), (qr; qs), (qs; qt), (qt; qu).

Анализ таблицы показывает, что

1) состояния qp и qr совместимы, т.к. при приеме каждого символа входного алфавита состояния автомат переходят в неотличимые пары состояний;

2) состояния qs и qt совместимы, т.к. при приеме каждого символа входного алфавита автомат переходит в одну и ту же пару неотличимых состояний;

3) состояния qr и qs не совместимы, т.к. при приеме символа x2 автомат переходит в разные пары неотличимых состояний, т.е. различимы между собой по выходу;

4) состояния qt и qu не совместимы, т.к. при приеме каждого символа входного алфавита автомат переходит в разные пары неотличимых состояний, т.е. они различимы между собой по выходу для каждого входного символа.

Таблица 1.22.

неотличимые состояния (q; q)	символы входного алфавита xОX
	x1	x2	…	xn
…	…	…	…	…
(qp; qr)	(qp; qr)	(qs; qt)	…	(qt; qu)
(qr; qs)	(qp; qr)	(qs; qu)	…	(qp; qr)
(qs; qt)	(qp; qr)	(qp; qr)	…	(qp; qr)
(qt; qu)	(qp; qs)	(qr; qt)	…	(qs; qu)
…	…	…	…	…

Множество совместимых состояний, имеющих одинаковые значения функций переходов для каждого символа xkОX, формируют классы эквивалентных состояний. Так по таблице 1.22 формируются классы эквивалентных состояний Q» 1={qp, qr} и Q» 2={qs, qt}, каждый из которых можно заместить одним состоянием q'1«{qp; qr} и q'2«{qs; qt}. Множество несовместимых состояний формируют классы отличимых состояний. Например, Q''3=qu. Множество классов называется минимальным, если все внутренние состояния автомата принадлежат минимальному числу согласованных и отличимых классов. В данном примере минимальный автомат представляют три класса: Q «1={qp; qr}, Q» 2={qs; qt} и Q''3=qu. Состояния каждого класса можно «склеить» в одно состояние q' и заполнить таблицы переходов и выходов известными значениями функций состояний соответствующего класса.

Пример 1.6. Пусть дан автомат M=бX; Y; Q;y;jс,--где--X={0; 1}, Y={0; 1}, Q={q1; q2; q3; q4; q5}, y и--j (см. таблицу 1.23). Найти эквивалентные состояния автомата.

Множество неотличимых пар по условию j(qi; xk) =j(qj; xk) для каждой пары состояний (qi; qj)О(QДQ) есть (q1; q2), (q1; q3), (q1; q4), (q2; q3), (q2; q4) и (q3; q4).

В это множество можно включить (q2; q1), (q3; q1), (q4; q1), (q3; q2), (q4; q2) и (q4; q3). Однако, очевидно, что отношение неотличимости симметрично. Поэтому симметричные пары состояний не следует включать в таблицу переходов пар неотличимых состояний.

Множеству неотличимых пар принадлежат также (q1; q1), (q2; q2), (q3; q3), (q4; q4) и (q5; q5), так как отношение неотличимости рефлексивно. Такие пары не следует включать в левый столбец таблиц переходов пар неотличимых состояний, но следует помнить при анализе позиций таблицы.

Таблица 1.23.

текущее состояние qОQ	символы входного алфавита xОX
	0	1
q1	q1; 1	q2; 0
q2	q1; 1	q3; 0
q3	q5; 1	q1; 0
q4	q4; 1	q2; 0
q5	q4; 1	q3; 1

Для формирования класса неотличимых состояний следует проверить отношение неотличимости по условиям транзитивности. Все множество неотличимых пар примера удовлетворяет этому условию. Поэтому формируется один класс неотличимых состояний Q'1={q1, q2, q3, q4}, Для состояния q5 нет другого состояния, формирующего неотличимую пару. Поэтому состояние q5 формирует класс отличимых состояний Q'2=q5.

При этом выполняются условия Q'1ИQ'2=Q и Q'1ЗQ'2=Ж.

Для поиска совместимых состояний построим таблицу переходов пар неотличимых состояний (см. таблицу 1.24).

Таблица 1.24.

неотличимые состояния (qi; qj)	символы входного алфавита xОX
	0	1
(q1; q2)	(q1; q1)	(q2; q3)
(q1; q3)	(q1; q5)	(q1; q2)
(q1; q4)	(q1; q4)	(q2; q2)
(q2; q3)	(q1; q5)	(q1; q3)
(q2; q4)	(q1; q4)	(q2; q3)
(q3; q4)	(q4; q5)	(q1; q2)

Анализ таблицы показывает, что для входного символа «0» неотличимые пары (q1; q3) и (q2; q3) переходят в пару различимых состояний q1ОQ'1 и q5ОQ'2, а пара (q3; q4) - в пару различимых q4ОQ'1 и q5ОQ'2. Поэтому пары (q1; q3), (q2; q3) и (q3; q4) следует удалить из числа претендентов на совместимость (из левого столбца таблицы) и составить таблицу 1.25. Неотличимые пары, обусловливающие переход в пары различимых состояний, подчеркнуты в таблице 1.24.

Таблица 1.25.

неотличимые состояния (qi; qj)	символы входного алфавита xОX
	0	1
(q1; q2)	(q1; q1)	(q2; q3)
(q1; q4)	(q1; q4)	(q2; q2)
(q2; q4)	(q1; q4)	(q2; q3)

Анализ таблицы показывает, что для входного символа «1» неотличимые пары (q1; q2) и (q2; q4) переходят в удаленную на предыдущем этапе неотличимую пару (q2; q3). Поэтому пары (q1; q2) и (q2; q4) следует удалить из числа претендентов на совместимость (из левого столбца таблицы) и составить таблицу 1.26. Неотличимые пары, обусловливающие переход в пары различимых состояний, подчеркнуты в таблице 1.25.

Таблица 1.26.

неотличимые состояния (qi; qj)	символы входного алфавита xОX
	0	1
(q1; q4)	(q1; q4)	(q2; q2)

Анализ таблицы показывает, что состояния q1 и q4 формируют класс неотличимых и совместимых состояний Q''i={q1, q4}, то есть они эквивалентны.

4. Алгоритм минимизации детерминированного автомата.

Если эквивалентные состояния автомата заместить одним состоянием, то получим автомат с меньшим числом состояний. Автомат, среди состояний которого нет эквивалентных, называют минимальным. Поиск минимального автомата предусматривает отыскание неотличимых и совместимых состояний, формирование их классов и анализ значений функций переходов y:(QДX)®Q и выходов j:(QДX)®Y по представителям этих классов.

Алгоритм минимизации числа состояний автомата:

шаг 1: выделить в таблице выходов неотличимые состояния по правилу:

«если среди множества состояний qОQ найти такие qi и qj, у которых значения функции выходов одинаковы для каждого символа входного алфавита xkОX, т.е. j(qi; xk)=j(qj; xk), то состояния qi и qj являются неотличимыми»;

в результате анализа всех пар (qi; qj)О(QДQ) по таблице 1.27 можно выделить пары неотличимых состояний: (qp; qt), (qr; qs), (qr; qu), (qs; qu);

шаг 2: сформировать на множестве пар неотличимых состояний классы неотличимых состояний по правилу:

«если среди множества пар неотличимых состояний существуют пары (qi; qj), (qj; qk) и (qi; qk), то есть выполняется условие транзитивности для отношения неотличимости, то множество состояний {qi; qj; qk} формируют класс неотличимых состояний Q'i={qi; qj; qk}»;

в результате анализа множества неотличимых пар сформированы классы неотличимых состояний Q'1={qr; qs; qu} и Q'2={qp; qt} и класс отличимых состояний - Q'3=qv; при этом Q'1ИQ'2ИQ'3=Q и Q'1ЗQ'2=Q'1ЗQ'3=Q'2ЗQ'3=Ж;

шаг 3: составить таблицу переходов пар неотличимых состояний по правилу:

«левый столбец таблицы 1.29 представить парами неотличимых состояний, которые для удобства анализа сгруппировать по классам; позиции таблицы 1.29 заполнить парами значений функций переходов (y(qi; xk);y(qj; xk)) для каждой неотличимой пары (qi; qj) и для каждого символа входного алфавита xkОX по данным таблицы 1.28»;

Таблица 1.29.

неотличимые состояния (qi; qj)	символы входного алфавита xОX
	x1	x2	…	xn
(qr; qs)ОQ'1	(qp; qt)	(qt; qp)	…	(qr; qs)
(qr; qu)ОQ'1	(qp; qp)	(qt; qv)	…	(qr; qt)
(qs; qu)ОQ'1	(qt; qp)	(qp; qv)	…	(qs; qt)
(qp; qt)ОQ'2	(qr; qs)	(qv; qv)	…	(qt; qp)

шаг 4: выделить в таблице переходов пар неотличимых состояний совместимые состояния по правилу: «если для пары (qi; qj) и для каждого символа xkОX значения функций (y(qi; xk);y(qj; xk)) принадлежат общему классу неотличимости, то пара (qi; qj) совместима; если для пары (qi; qj) и хотя бы для одного xk ОX значения функций (y(qi; xk);y(qj; xk)) принадлежат различным классам неотличимости, то пара (qi; qj) несовместима и ее следует удалить из левого столбца таблицы переходов пар неотличимых состояний; процедуру повторять до тех пор, пока все состояния каждого класса неотличимости не станут совместимыми»;

по данным таблицы 1.29 несовместимыми являются состояния пары (qr; qu) и (qs; qu) класса Q'1, так как для x2 значения функций переходов принадлежат различным классам: (y(qr; x2)=qtОQ'2; y(qu; x2)=qvОQ'3) и (y(qs; x2)=qpОQ'2; y(qu; x2)=qvОQ'3), а состояния пары (qr; qs) класса Q'1 являются совместимыми, так как значения функций переходов для каждого символа входного алфавита принадлежат одному классу (y(qr; x1)=qpОQ'2;y(qs; x1)=qtОQ'2), (y(qr; x2)=qtОQ'2;y(qs; x2)=qpОQ'2),… и (y(qr; xn)=qrОQ'1;y(qs; xn)=qsОQ'1);

шаг 5: сформировать на множестве пар совместимых состояний классы совместимых состояний по правилу:

«если среди множества пар совместимых состояний существуют пары (qi; qj), (qj; qk) и (qi; qk), то есть выполняется условие транзитивности для отношения совместимости, то множество состояний {qi; qj; qk} формирует класс совместимых состояний Q'i= {qi; qj; qk}»;

анализ классов неотличимых состояний показывает, что класс Q'2 является классом совместимых состояний, а из класса неотличимых состояний Q'1 cледует удалить состояние qu, оформив два класса совместимых состояний Q» 1={qs; qr} и Q» 2=qu;

шаг 6: если в результате анализа всех пар неотличимых состояний для каждого символа входного алфавита xkОX найдены классы совместимых и несовместимых состояний, то конец иначе перейти к шагу 3;

шаг 7: состояния каждого класса совместимых состояний замещаются эквивалентным состоянием q'i«{qi; qj}, а несовместимые и отличимые состояния сохраняют свое значение в описании минимального автомата.

Пример 1.7. Для детерминированного автомата M=бX; Y; Q;y;jс, где--X={0; 1}, Y={0; 1}, Q={q1; q2; q3; q4; q5; q6; q7; q8; q9}, а функции y--и j--заданы таблицей поведения (см. таблицу 1.30). Найти минимальный автомат.

Таблица 1.30.

текущее состояние qОQ	символы входного алфавита xОX
	0	1
q1	q9; 1	q1; 1
q2	q2; 1	q2; 0
q3	q7; 0	q5; 1
q4	q2; 1	q2; 0
q5	q2; 1	q2; 0
q6	q3; 1	q9; 0
q7	q6; 1	q8; 0
q8	q9; 1	q9; 0
q9	q4; 0	q6; 0

Для изображения структуры абстрактного автомата удобно представить таблицу соединений состояний исходного автомата и его граф (см. таблицу 1.31 и рис. 1.15).

Таблица 1.31.

текущее состояние qОQ	очередное состояние qОQ
	q1	q2	q3	q4	q5	q6	q7	q8	q9
q1	1/1	-	-	-	-	-	-	-	0/1
q2	0/1	1/0	-	-	-	-	-	-	-
q3	-	-	-	-	1/1	-	0/0	-	-
q4	-	(0/1Ъ1/0)	-	-	-	-	-	-	-
q5	-	(0/1Ъ1/0)	-	-	-	-	-	-	-
q6	-	-	0/1	-	-	-	-	-	1/0
q7	-	-	-	-	-	0/1	-	1/0	-
q8	-	-	-	-	-	-	-	-	(0/1Ъ1/0)
q9	-	-	-	0/0	-	1/0	-	-	-

Рис. 1.15. Граф детерминированного автомата

Анализ множества состояний детерминированного автомата по значениям функции выхода для каждого символа входного алфавита xkОX позволяет выделить четыре класса: Q'1=q1, Q'2=q3, Q'3=q9 и Q'4={q2; q4; q5; q6; q7; q8}.

Множество пар неотличимых состояний может быть найдено только для класса Q'4: (q2; q4); (q2; q5); (q2; q6); (q2; q7); (q2; q8); (q4; q5); (q4; q6); (q4; q7); (q4; q8); (q5; q6); (q5; q7); (q5; q8); (q6; q7); (q6; q8); (q7; q8). По этому множеству составим таблицу переходов пар состояний (cм. таблицу 1.32).