В. 9 Эквивалентные автоматы.

 

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

 

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

 

            Автоматы М и М1 называются эквивалентными, если для каждого состояния автомата М существует эквивалентное ему состояние автомата М1 и наоборот.

 

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

 

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

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

           

            Автомат, эквивалентный заданному и имеющий наименьшее из всех возможных число состояний называется минимальным.

 

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

 

Пусть имеется автомат с множеством внутренних состояний Q, среди которых могут быть эквивалентные. Отношение эквивалентности состояний обладает обычными свойствами эквивалентности: рефлексивностью, симметричностью и транзитивностью. Поэтому множество Q можно разбить на классы эквивалентности.

 

Например: пусть имеется автомат, заданный таблицей (автомат преобразователь, а не распознаватель).

	q1	q2	q3	q4	q5	q6
0	q1,1	q2,0	q1,1	q1,1	q6,0	q5,0
1	q5,0	q2,0	q2,0	q3,0	q6,0	q6,0
2	q1,0	q6,1	q3,0	q3,0	q5,1	q2,1

 

На основе этой таблицы составим другую таблицу, клетки которой будут соответствовать различным парам q(i)  q(j) (i!=j), заполнив ее согласно следующим правилам:

-         если два состояния q(i)  q(j) неэквивалентны (т. е. Для какого то значения входного символа х значения на выходе различаются), то соответствующая клетка зачеркивается;

-         если в состояниях q(i)  и q(j) для каждого х значения на выходе одинаковы, то в клетках записываются все пары состояний q(v) q(w) (v!=w), отличные от q(i)  q(j), в которые автомат может перейти из q(i) и q(j) при подаче одного и того же входного сигнала.

 

	q1	q2	q3	q4	q5
q2	X	-	-	-	-
q3	q5 q2	X	-	-	-
q4	q5 q3 q1 q3	X	q2 q3	-	-
q5	X	q2 q6 q6 q5	X	X	-
q6	X	q2 q5	X	X	q5 q2

* X в таблице – это хуй, т. е. клетка зачеркнута (прим. автора...)

 

Эквивалентны: q1 q3, q1 q4, q2 q5, q2 q6, q3 q4, q5 q6;

Попарно эквивалентны: {q1,q3}, {q2,q5,q6};

Все остальные эквивалентны лишь сами себе {q4}.

 

После выделения классов эквивалентности состояний для автомата М можно построить эквивалентный ему автомат М1. В качестве алфавитов для М1 возьмем соответствующие алфавиты из М, а каждому классу эквивалентных состояний поставим в соответствие одно состояние из М1, т. е. (q1)1↔{q1,q2}; (q2)1↔{q2,q5,q6}; и т.д.

 

Окончательно таблицу можно представить следующим образом:

	(q1)1	(q2)1	(q3)1
0	(q3)1,1	(q2)1,0	(q3)1,1
1	(q2)1,0	(q2)1,0	(q1)1,0
2	(q1)1,0	(q2)1,1	(q1)1,0

 

Можно доказать следующую теорему:

 

            Для всякого конечного автомата существует единственный эквивалентный ему минимальный автомат. Существует алгоритм, который любому заданному конечному автомату строит соответствующий минимальный.

С точки зрения распознавания формальных языков.

 

            Два конечных автомата называются эквивалентными если они распознают один и тот же язык.