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

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

(q_i; x_k) = (q_j;x_k), (1.32)

то состояния q_i и q_j автомата М формируют неотличимую пару (q_i;q_j)(QQ).

Множество неотличимых пар (q_i;q_j)(QQ), имеющих одинаковые значения функций выходов для каждого символа x_kX формирует класс неотличимых состояний Q'_i. Если множество неотличимых пар содержит пары (q_i;q_j), (q_j;q_k) и (q_i;q_k), то есть выполняется условие транзитивности для отношения неотличимости, то класс неотличимых состояний формирует множество Q'_i={q_i;q_j;q_k}.

Если для неотличимой пары состояний (q_i;q_j) значения функций переходов формируют для всех символов x_kX также пары неотличимых состояний ((q_i[];x_k[]);(q_j[];x_k[])), то такие состояния q_i и q_j называют совместимыми.

Множество совместимых пар, имеющих одинаковые значения функций переходов для каждого символа x_kX, формирует класс совместимых состояний Q''_i. Если множество совместимых пар содержит пары (q_i;q_j), (q_j;q_k) и (q_i;q_k), то есть выполняется условие транзитивности для отношения совместимости, то класс совместимых состояний есть Q''_i={q_i;q_j;q_k}.

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

Для поиска эквивалентных состояний автомата М также следует заполнить таблицу переходов пар неотличимых состояний. Левый столбец таблицы предназначен для указания пар неотличимых состояний (q_i;q_j)(QQ), которые определяют по таблице выходов для всех x_kX по условию (q_i;x_k)=(q_j;x_k). Позициями этой таблицы являются пары ((q_i;x_k);(q_j;x_k)), в которые переходит автомат из неотличимой пары (q_i;q_j) для каждого символа x_kX. Значения ((q_i;x_k);(q_j;x_k)) определяются по таблице переходов автомата М.

Пусть таблица переходов пар состояний одного автомата представлена таблицей 1.22, где множество пар неотличимых состояний есть (q_p;q_r), (q_r;q_s), (q_s;q_t), (q_t;q_u).

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

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

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

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

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

Таблица 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)
…	…	…	…	…

Множество совместимых состояний, имеющих одинаковые значения функций переходов для каждого символа x_kX, формируют классы эквивалентных состояний. Так по таблице 1.22 формируются классы эквивалентных состояний Q''₁={q_p,q_r} и Q''₂={q_s,q_t}, каждый из которых можно заместить одним состоянием q'₁{q_p;q_r} и q'₂{q_s;q_t}. Множество несовместимых состояний формируют классы отличимых состояний. Например, Q''₃=q_u. Множество классов называется минимальным, если все внутренние состояния автомата принадлежат минимальному числу согласованных и отличимых классов. В данном примере минимальный автомат представляют три класса: Q''₁={q_p;q_r}, Q''₂={q_s;q_t} и Q''₃=q_u. Состояния каждого класса можно "склеить" в одно состояние q' и заполнить таблицы переходов и выходов известными значениями функций состояний соответствующего класса.

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

Множество неотличимых пар по условию (q_i;x_k) =(q_j;x_k) для каждой пары состояний (q_i;q_j)(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₂), (q₃;q₃), (q₄;q₄) и (q₅;q₅), так как отношение неотличимости рефлексивно. Такие пары не следует включать в левый столбец таблиц переходов пар неотличимых состояний, но следует помнить при анализе позиций таблицы.

Таблица 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'₁={q₁,q₂,q₃,q₄}, Для состояния q₅ нет другого состояния, формирующего неотличимую пару. Поэтому состояние q₅ формирует класс отличимых состояний Q'₂=q₅.

При этом выполняются условия Q'₁Q'₂=Q и Q'₁Q'₂=.

Для поиска совместимых состояний построим таблицу переходов пар неотличимых состояний (см. таблицу 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" неотличимые пары (q₁;q₃) и (q₂;q₃) переходят в пару различимых состояний q₁Q'₁ и q₅Q'₂, а пара (q₃;q₄) - в пару различимых q₄Q'₁ и q₅Q'₂. Поэтому пары (q₁;q₃), (q₂;q₃) и (q₃;q₄) следует удалить из числа претендентов на совместимость (из левого столбца таблицы) и составить таблицу 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" неотличимые пары (q₁;q₂) и (q₂;q₄) переходят в удаленную на предыдущем этапе неотличимую пару (q₂;q₃). Поэтому пары (q₁;q₂) и (q₂;q₄) следует удалить из числа претендентов на совместимость (из левого столбца таблицы) и составить таблицу 1.26. Неотличимые пары, обусловливающие переход в пары различимых состояний, подчеркнуты в таблице 1.25.

Таблица 1.26.

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

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

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

1) Начертить граф и найти эквивалентные состояния автомата, описанного таблицей:

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

2) Начертить граф и найти эквивалентные состояния автомата, описанного таблицей:

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

3) Начертить граф и найти эквивалентные состояния автомата, описанного таблицей:

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