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

Поиск минимального недетерминированного автомата усложняется тем, что в таблицах переходов и выходов есть неопределенные позиции. Однако, анализ функций переходов :QX)Q и выходов QX)Y позволяет находить неотличимые и совместимые состояния даже при наличии неопределенных позиций, а последующее согласование совместимых классов - находить эквивалентные состояния. Пусть функции выходов и переходов недетерминированного автомата заданы таблицами 1.47 и 1.48.

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

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

"а) если среди множества пар состояний автомата (q_i;q_j)(QQ) можно найти такие q_i и q_j, для которых значения функций выходов (q_i;x_k) и (q_j;x_k) определены для x_kX и они совпадают, то есть (q_i;x_k)(q_j;x_k), или значение одной из функций для x_kX покрывает безразличную позицию другой, или значения обеих функций не определены для x_kX, то пару (q_i;q_j) считать парой неотличимых состояний;

b) если среди множества пар (q_i;q_j)(QQ) можно найти такие q_i и q_j, для которых значения функции выходов (q_i;x_k) и (q_j;x_k) различны хотя бы для одного x_kX, т. е. (q_i;x_k)(q_j;x_k), то пару (q_i;q_j) считать парой отличимых состояний";

в результате анализа таблицы 1.47 парами неотличимых состояний являются (q_p;q_t), (q_p;q_v), (q_r;q_u), (q_r;q_s), (q_s;q_u), а парами отличимых состояний - (q_p;q_r), (q_p;q_s), (q_p;q_u), (q_r;q_t), (q_r;q_v), (q_s;q_t), (q_s;q_v), (q_t;q_u) и (q_t;q_v).

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

"а) если среди множества пар неотличимых состояний существуют пары (q_i;q_j), (q_j;q_k) и (q_i;q_k), то множество {q_i;q_j;q_k} формирует класс неотличимых состояний Q'_i ={q_i;q_j;q_k} ( условие транзитивности);

b) если среди множества пар неотличимых состояний существуют пары (q_i;q_j), (q_j;q_k) и не существует пара (q_i;q_k), то пары (q_i;q_j) и (q_j;q_k) формируют два класса неотличимых состояний Q'_l={q_i;q_j} и Q'_k={q_j;q_k} (состояние q_j принадлежит двум классам)";

в результате анализа множества неотличимых пар сформированы классы неотличимых состояний Q'₁={q_r;q_s;q_u}, Q'₂={q_p;q_t} и Q'₃={q_p;q_v}; при этом Q'₁Q'₂Q'₃=Q, Q'₁Q'₂=, Q'₁Q'₃=,но Q'₂Q'₃;

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

"левый столбец таблицы представить парами неотличимых состояний, которые сгруппированы по классам неотличимости; позиции таблицы заполнить для каждой неотличимой пары (q_i;q_j) и для каждого символа x_kX по таблице переходов парами значений ((q_i;x_k);(q_j;x_k)); если хотя бы одно из значений функции переходов (q_i;x_k) или (q_j;x_k) имеет значение "_*", то паре ((q_i;x_k);(q_j;x_k)) присвоить также значение "_*""; (смотри таблицу 1.49);

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

"если для пары неотличимых состояний (q_i;q_j) значения функции переходов ((q_i;x_k);(q_j;x_k)) для x_kX принадлежат также множеству пар неотличимых состояний (левому столбцу таблицы), то состояния q_i и q_j совместимы, иначе пару (q_i;q_j) удалить из множества пар неотличимых состояний ( из левого столбца таблицы)";

в результате анализа можно установить, что совместимыми парами являются (q_p;q_v), (q_r;q_s), (q_s;q_u), (q_p;q_t) и (q_r;q_u).

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

"а) если множеству совместимых пар принадлежат пары (q_i;q_j), (q_j;q_k) и (q_i;q_k), т.е. выполняется условие транзитивности, то состояния q_i, q_j и q_k формируют класс совместимых состояний Q'_i={q_i;q_j;q_k;...};

b) если множеству совместимых пар принадлежат (q_i;q_j), (q_j;q_k) и не принадлежит (q_i;q_k), т.е. не выполняется условие транзитивности, то состояния q_i,q_j и q_k формируют два класса совместимых состояний Q'_i= {q_i;q_j;...} и Q'_j={q_j;q_k;...}";

в результате анализа множества совместимых пар выявлены классы совместимости Q'₂={q_p;q_t}, Q'₃={q_p;q_v}, Q'₄={q_u;q_v},Q'₅={q_r;q_s} и Q'₆=(q_s;q_u}

шаг 6: найти наименьшее множество совместимых классов, покрывающих все исходные состояния автомата:

(Q'₂Q'₄Q'₅) = {q_p;q_r;q_s;q_t;q_u;q_v}.

шаг 7: на множестве классов совместимых состояний, выбранных на шаге 6, найти согласованные состояния:

"если для любого класса наименьшего множества совместимых состояний и любых его элементов q_i и q_j значения функций переходов (q_i;x_k) и (q_j;x_k) принадлежат одному совместимому классу для всех символов x_kX, то такие классы являются согласованными и следует перейти к шагу 8, иначе перейти к шагу 6 и найти другое наименьшее множество классов совместимых состояний, покрывающее все исходные состояния автомата";

в результате анализа таблицы 1.49 установлено, что все состояния согласованы в минимальном наборе классов совместимых состояний Q'₂, Q'₄, Q'₅;

шаг 8: состояния каждого класса согласованных состояний "склеить" и заместить эквивалентным состоянием; отличимые и несовместимые состояния сохраняют свое значение в описании минимального автомат;

для состояний каждого класса наименьшего набора согласованных состояний ввести эквивалентные состояния: q'₁{q_p;q_t}, q'₂{q_p;q_v}, q'₃{q_u;q_v}, q'₄{q_r;q_s} и q'₅{q_s;q_u} и составить таблицы переходов и выходов.

Пример 1.9. Для недетерминированного автомата M = X;Y;Q;, гдеX={x₁;x₂;x₃;x₄}, Y={0;1}, Q={q₁;q₂;q₃;q₄;q₅}, функции и заданы таблицей поведения (см. таблицу 1.53) . Найти минимальный автомат.

Таблица 1.53.

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

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

Таблица 1.54.

текущее состояние qQ		очередное состояние qQ
		q1		q2		q3		q4		q5
q1	—		(x1/0x4/ *)		x3/ *		—		—
q2	—		x3/0		x1/0		—		x2/1
q3	—		—		x1/0		x2/1		x4/0
q4	x2/1		x3/ *		—		—		—
q5	x3/1		—		—		—		—

Согласно алгоритма имеем множество неотличимых пар: (q₁;q₂), (q₁;q₃), (q₁;q₄), (q₁;q₅), (q₂;q₃), (q₂;q₄), (q₃;q₄), (q₃;q₅), (q₄;q₅) и отличимую пару - (q₂;q₅); классы неотличимых состояний: Q'₁={q₁;q₂;q₃;q₄} и Q'₂={q₁;q₃;q₄;q₅} и таблицу переходов пар неотличимых состояний (см. таблицу 1.55).

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

Таблица 1.55.

неотличимые состояния (q;q)	символы входного алфавита xX
	x1	x2	x3	x4
(q1;q2)	(q2;q3)	*	(q2;q3)	*
(q1;q3)	(q2;q3)	*	*	(q2;q5)
(q1;q4)	*	*	(q2;q3)	*
(q1;q5)	*	*	(q1;q3)	*
(q2;q3)	(q3;q3)	(q4;q5)	*	*
(q2;q4)	*	(q1;q5)	(q2;q2)	*
(q3;q4)	*	(q1;q4)	*	*
(q3;q5)	*	*	*	*
(q4;q5)	*	*	(q1;q2)	*

Анализ таблицы 1.55 показывает, что для символа "x₄" пара неотличимых состояний (q₁;q₃) переходит в пару отличимых состояний (q₂;q₅); следовательно, пара (q₁;q₃) не претендует на совместимость состояний q₁ и q₃, ее следует удалить из левого столбца и составить новую таблицу переходов - таблицу 1.56.

Таблица 1.56.

неотличимые состояния (q;q)	символы входного алфавита xX
	x1	x2	x3	x4
(q1;q2)	(q2;q3)	*	(q2;q3)	*
(q1;q4)	*	*	(q2;q3)	*
(q1;q5)	*	*	(q1;q3)	*
(q2;q3)	(q3;q3)	(q4;q5)	*	*
(q2;q4)	*	(q1;q5)	(q2;q2)	*
(q3;q4)	*	(q1;q4)	*	*
(q3;q5)	*	*	*	*
(q4;q5)	*	*	(q1;q2)	*

Анализ таблицы 1.56 показывает, что для символа "x₃" пара неотличимых состояний (q₁;q₅) переходит в удаленную пару (q₁;q₃); следовательно, пара (q₁;q₅) также не претендует на совместимость состояний q₁ и q₅, ее следует удалить из левого столбца и составить новую таблицу переходов - таблицу 1.57.

Таблица 1.57.

неотличимые состояния (q;q)	символы входного алфавита xX
	x1	x2	x3	x4
(q1;q2)	(q2;q3)	*	(q2;q3)	*
(q1;q4)	*	*	(q2;q3)	*
(q2;q3)	(q3;q3)	(q4;q5)	*	*
(q2;q4)	*	(q1;q5)	(q2;q2)	*
(q3;q4)	*	(q1;q4)	*	*
(q3;q5)	*	*	*	*
(q4;q5)	*	*	(q1;q2)	*

Анализ таблицы 1.57 показывает, что для символа "x₂" пара неотличимых состояний (q₂;q₄) переходит в удаленную пару (q₁;q₅); следовательно, пара (q₂;q₄) также не претендует на совместимость состояний q₂ и q₄, ее следует удалить из левого столбца и составить новую таблицу переходов - таблицу 1.58.

Таблица 1.58.

неотличимые состояния (q;q)	символы входного алфавита xX
	x1	x2	x3	x4
(q1;q2)	(q2;q3)	*	(q2;q3)	*
(q1;q4)	*	*	(q2;q3)	*
(q2;q3)	(q3;q3)	(q4;q5)	*	*
(q3;q4)	*	(q1;q4)	*	*
(q3;q5)	*	*	*	*
(q4;q5)	*	*	(q1;q2)	*

Анализ таблицы 1.58 показывает, что для символа "x₁" пары неотличимых состояний переходят также в пары неотличимых состояний; следовательно, в левом столбце таблицы остались только пары совместимых состояний;

Согласно алгоритма найдены классы совместимых состояний: Q''₁={q₁;q₂}, Q''₂={q₁;q₄}, Q''₃={q₂;q₃} и Q''₄={q₃;q₄;q₅}.

Так как q₃ и q₄ входят в разные класса совместимых состояний, то следует выделить в Q”₄ подклассы для определения согласованных классов:

а) Q''₄={q₃;q₅}q₄, где {q₃;q₅}=Q''₄₁;

b) Q''₄={q₄;q₅}q₃, где {q₄;q₅}=Q''₄₂.

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

а) пусть Q''₁={q₁;q₂} и Q''₄={q₃;q₄;q₅};

анализ таблицы 1.59 показывает, что выбранные классы не согласованы, так как для символов x₁ и x₃ класс совместимых состояний Q''₁ переходит в различные классы Q''₁ и Q''₄;

b) пусть Q''₁={q₁;q₂}, Q''₂={q₁;q₄} и Q''₄₁={q₃;q₅};

анализ таблицы 1.60 показывает, что выбранные классы не согласованы, так как для символов x₁ и x₃ класс совместимых состояний Q''₁ переходит в различные классы Q''₁ и Q''₄₁;

c) пусть Q''₁={q₁;q₂}, Q''₃={q₂;q₃} и Q''₄₂={q₄;q₅};

анализ таблицы 1.61 показывает, что выбранные классы согласованы, так как для любого символа все классы совместимых состояний переходят в один класс совместимых состояний;

Введем обозначения для состояний, замещающих согласованные классы: q'₁{q₁;q₂}, q'₂{q₂;q₃}, q'₃{q₄;q₅}. Таблица 1.62 отображает поведение минимального автомата, а рис. 20 - граф автомата.

Таблица 1.59.

класс согласованных состояний Q'i	символы входного алфавита xX
	x1	x2	x3	x4
Q''1	Q''1;Q''4	*	Q''1;Q''4	*
Q''4	*	Q''1;Q''4	Q''1	*

Таблица 1.60.

класс согласованных состояний Q'i	символы входного алфавита xX
	x1	x2	x3	x4
Q''1	Q''1;Q''41	*	Q''1;Q''41	*
Q''2	*	*	Q''1;Q''41	*
Q''41	*	*	*	*

Таблица 1.61.

класс согласованных состояний Q'i	символы входного алфавита xX
	x1	x2	x3	x4
Q''1	Q''3	*	Q''3	*
Q''3	Q''3	Q''42	*	*
Q''42	*	*	Q''1	*

Таблица 1.62.

текущее состояние qQ	символы входного алфавита xiX
	x1	x2	x3	x4
q'1	q'2;0	q'3;1	q'2;0	q'1;*
q'2	q'2;0	q'3;1	q'1;0	q'3;0
q'3	* ; *	q'1;1	q'1;1	* ; *

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

Следует обратить внимание, что в результате минимизации автомата сохранились неопределенными переходы для состояния q'3.

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

а) пусть = (x₁x₂x₃x₄), тогда

для исходного автомата: для минимального автомата:

вход: x₁ - x₂ - x₃ - x₄; вход: x₁ - x₂ - x₃ - x₄;

q: q₁ - q₂ - q₅ - q₁ - q₂; q: q'₁ - q'₂ - q'₃ - q'₁ - q'₁;

выход: 0 - 1 - 1 - _*; выход: 0 - 1 - 1 - _*;

то есть (011_*); то есть (011_*);

b) пусть =(x₄x₃x₂x₁), тогда

для исходного автомата: для минимального автомата:

вход: x₄ - x₃ - x₂ - x₁; вход: x₄ - x₃ - x₂ - x₁;

q: q₁ - q₂ - q₂ - q₅ - _*; q: q'₁ - q'₁ - q'₂ - q'₃ - _*;

выход: _* - 0 - 1 - _*; выход: _* - 0 - 1 - _*;

то есть (_*01_*); то есть (_*01_*);

c) пусть =(x₁x₂x₁x₂), тогда

для исходного автомата: для минимального автомата:

вход: x₁ - x₂ - x₁ - x₂; вход: x₁ - x₂ - x₁ - x₂;

q: q₁ - q₂ - q₅ - _*; q: q'₁ - q'₂ - q'₃ - _*;

выход: 0 - 1 - _*; выход: 0 - 1 - _*;

то есть (01_*); то есть (01_*);

Так подтверждается эквивалентность исходного и минимального недетерминированных автоматов.

Пример 1.10. Для недетерминированного автомата M=X;Y;Q;, гдеX={0;1}, Y={0;1}, Q={q₁;q₂;q₃;q₄;q₅;q₆}, функции и заданы таблицей 1.63. Найти минимальный автомат.

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

а)пусть = (x₁x₂x₃x₄), тогда

для исходного автомата: для минимального автомата:

вход: x₁ - x₂ - x₃ - x₄; вход: x₁ - x₂ - x₃ - x₄;

q: q₁ - q₂ - q₅ - q₁ - q₂; q: q'₁ - q'₂ - q'₃ - q'₁ - q'₁;

выход: 0 - 1 - 1 - _*; выход: 0 - 1 - 1 - _*;

то есть (011_*); то есть (011_*);

b)пусть =(x₄x₃x₂x₁), тогда

для исходного автомата: для минимального автомата:

вход: x₄ - x₃ - x₂ - x₁; вход: x₄ - x₃ - x₂ - x₁;

q: q₁ - q₂ - q₂ - q₅ - _*; q: q'₁ - q'₁ - q'₂ - q'₃ - _*;

выход: _* - 0 - 1 - _*; выход: _* - 0 - 1 - _*;

то есть (_*01_*); то есть (_*01_*);

Таблица 1.63.

текущее состояние qQ	символы входного алфавита xiX
	x1	x2
q1	q2;0	* ; *
q2	q1;0	q6;*
q3	q4;1	* ; *
q4	q5;0	q3;0
q5	* ; *	q6; *
q6	q4;0	* ; *

Соединения состояний автомата представлены таблицей 1.64, а граф - рис.1.21.

Таблица 1.64.

текущее состояние qQ	очередное состояние qQ
	q1	q2	q4	q4	q5	q6
q1	—	0/0	—	—	—	—
q2	0/0	—	—	—	—	1/*
q3	—	—	—	0/1	—	—
q4	—	—	1/0	—	0/0	—
q5	—	—	—	—	—	1/*
q6	—	—	—	0/0	—	—

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

шаг 1: множество неотличимых пар: (q₁;q₂), (q₁;q₄), (q₁;q₅), (q₁;q₆), (q₂;q₄), (q₂;q₅), (q₂;q₆), (q₃;q₅), (q₄;q₅), (q₄;q₆), (q₅;q₆); множество отличимых пар: (q₁;q₃), (q₂;q₃), (q₃;q₄), (q₃;q₆);

шаг 2: классы неотличимых состояний: Q'₁={q₁;q₂;q₄;q₅;q₆} и Q'₂={q₃;q₅}; при этом Q'₁Q'₂=Q, Q'₁Q'₂;

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

шаг 4: поиск совместимых состояний по таблицам 1.65 и 1.66:

Анализ таблицы 1.65 показывает, что для символа "1" пары неотличимых состояний (q₂;q₄) и (q₄;q₅) переходят в пару отличимых состояний (q₃;q₆); следовательно, эти пары не претендуют на совместимость, их следует удалить из левого столбца и составить новую таблицу переходов - таблицу 1.66; анализ таблицы 1.66 показывает, что для символа "0" пара неотличимых состояний (q₁;q₆) переходит в удаленную пару (q₂;q₄), а пара (q₄;q₆) - в удаленную пару (q₄;q₅); следовательно, пары (q₁;q₆) и (q₄;q₆) также не претендуют на совместимость, их следует удалить из левого столбца и составить новую таблицу переходов - таблицу 1.67.

В левом столбце таблицы 1.67 остались только пары совместимых состояний;

шаг 5: классы совместимых состояний: Q''₁={q₁;q₂;q₅}, Q''₂={q₂;q₅;q₆}, Q''₃={q₁;q₄} и Q''₄={q₃;q₅};

шаг 6: наименьшее число совместимых классов, покрывающее все совместимые пары состояний: Q''₁={q₁;q₂;q₅}, Q''₂={q₂;q₅;q₆}, Q''₃={q₁;q₄} и Q''₄={q₃;q₅};

шаг 7: таблица переходов совместимых классов – таблица 1.68.

шаг 8: состояния, замещающие состояния согласованных классов: q'₁{q₁;q₂;q₅}, q'₂{q₂;q₅;q₆}, q'₃{q₁;q₄} и q'₄={q₃;q₅}; таблица 1.69 отображает поведение минимального автомата, а рис. 1.22 - граф автомата.

Следует обратить внимание, что в результате минимизации автомата сохранились только безразличные выходные символы.

Таблица 1.65.

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

Таблица 1.66.

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

Таблица 1.67.

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

Таблица 1.68.

класс согласованных состояний Q'i	символы входного алфавита xX
	0	1
Q''1	Q''1	Q''2
Q''2	Q''3	*
Q''3	Q''1	*
Q''4	*	*

Таблица 1.69.

текущее состояние qQ	символы входного алфавита xiX
	0	1
q'1	q'1;0	q'2; *
q'2	q'3;0	q'2; *
q'3	q'1;0	q'4;0
q'4	q'3;1	q'2; *

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

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

а) пусть = (010011), тогда

для исходного автомата:	для минимального автомата:
вход: 0 - 1 - 0 - 0 - 1 - 1;	вход: 0 - 1 - 0 - 0 - 1 - 1;
q: q1 - q2 - q6 - q4 - q5 - q6 - *;	q: q'1 - q'1 - q'2 - q'3 - q'1 - q'2 - *;
выход: 0 - * - 0 - 0 - * - *;	выход: 0 - * - 0 - 0 - * - *;
то есть (0*00**);	то есть (0*00**);

b) пусть = (010101), тогда

для исходного автомата:	для минимального автомата:
вход: 0 - 1 - 0 - 1 - 0 - 1;	вход: 0 - 1 - 0 - 1 - 0 - 1;
q: q1 - q2 - q6 - q4 - q3 - q4 - q3;	q: q'1 - q'1 - q'2 - q'3 - q'4 - q'3 - q'4;
выход: 0 - * - 0 - 0 - 1 - 0;	выход: 0 - * - 0 - 0 - 1 - 0;
то есть (0*0010);	то есть (0*0010);

c) пусть = (101001), тогда

для исходного автомата:	для минимального автомата:
вход: 1 - 0 - 1 - 0 - 0 - 1;	вход: 1 - 0 - 1 - 0 - 0 - 1;
q: q1 - * …;	q: q'1 - q'2 - q'3 - q'4 - q'3 - q'2 - q'1;
выход: * …;	выход: * - 0 - 0 - 1 - 0 - *;
то есть (*, …);	то есть (*0010*);

Так показана одинаковость работы двух автоматов.

Контрольные вопросы и задачи.

1) Минимизировать число состояний автомата, заданного таблицей:

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

Начертить графы исходного и минимизированного автоматов.

2) Минимизировать число состояний автомата, заданного таблицей:

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

Начертить графы исходного и минимизированного автоматов.

4) Минимизировать число состояний автомата, заданного таблицей:

текущее состояние qQ	символы входного алфавита xX
	x1	x2	x3
q0	*;*	q0;0	q1;1
q1	*;*	q1;0	q0;0
q2	q2;0	q3;0	*;*
q3	q3;1	q4;0	*;*
q4	q4;2	q2;0	*;*
q5	q0;2	*;*	q0;2
q6	q1;1	*;*	q1;0

Начертить графы исходного и минимизированного автоматов.