 |
Эквивалентность внутренних состояний автомата
|
|
|
|
Особый интерес представляет анализ множества состояний одного автомата. Этот анализ позволяет минимизировать число внутренних состояний автомата и оптимизировать его структуру. При исполнении этой операции лсобое внимание следует обратить на различия между детерминироваанным и недетерминированным автоматами.
Детерминированный автомат
Если у автомата М есть состояния qi и qj, для которых значения функций выходов совпадают для всех символов множества X, то есть j(qi; xk) = j(qj; xk), то состояния 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 также пары неотличимых состояний ((yqi[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 автомата М неотличимы и совместимы, то они эквивалентны. Поэтому класс совместимых состояний есть класс эквивалентных состояний.
Для поиска эквивалентных состояний автомата М также следует заполнить таблицу переходов пар неотличимых состояний.
Таблица 6.17
| неотличимые состояния (qi; qj) | 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) |
|
|
|
В левом столбце таблицы указаны пары неотличимых состояний (qi; qj)Î(QÄQ), которые были определены по таблице выходов для всех xkÎX. Позициями этой таблицы являются пары (y(qi; xk); y(qj; xk)), в которые переходит автомат из неотличимой пары (qi; qj) для каждого символа xkÎX. Значения (y(qi; xk); y(qj; xk)) определяются по таблице переходов автомата.
Анализ таблицы показывает, что
· состояния qp и qr совместимы, т.к. при приеме каждого символа входного алфавита состояния автомат переходят в неотличимые пары состояний;
· состояния qs и qt совместимы, т.к. при приеме каждого символа входного алфавита автомат переходит в одну и ту же пару неотличимых состояний;
· состояния qr и qs не совместимы, т.к. при приеме символа x2 автомат переходит в разные пары неотличимых состояний, т. е. различимы между собой по выходу;
· состояния qt и qu не совместимы, т.к. при приеме каждого символа входного алфавита автомат переходит в разные пары неотличимых состояний, т.е. они различимы между собой для каждого входного символа.
Множество совместимых состояний, имеющих одинаковые значения функций переходов для каждого символа xkÎX, формируют классы эквивалентных состояний. Так по таблице 6.17 формируются классы эквивалентных состояний Q''1={qp,qr} и Q''2={qs,qt}.
Множество несовместимых состояний формируют классы отличимых состояний. Например, по таблице 6.17 такой класс один Q''3=qu.
Множество классов называется минимальным, если все внутренние состояния автомата принадлежат минимальному числу совместимых и отличимых классов. В данном примере минимальный автомат представляют три класса: Q''1={qp;qr}, Q''2={qs;qt} и Q''3=qu. Состояния совместимых классов можно заместить одним состоянием q'1«{qp; qr} и q'2«{qs; qt} и составить новые таблицы переходов и выходов минимального автомата.
|
|
|
Пример: дан автомат M=<X; Y; Q; y; j>, где X={0;1}, Y={0;1}, Q={q1;q2;q3;q4;q5}, а y, j представлены таблицей. Найти минимальный автомат.
| текущее состояние qÎQ | xÎX | |
| 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 |
По условию j(qi; xk)=j(qj; xk) найдем множество неотличимых пар: {(q1; q2), (q1; q3), (q1; q4), (q2; q3), (q2; q4) и (q3; q4)}.
При формировании классов следует проверить условие транзитивности. В данном примере формируется один класс неотличимых состояний Q'1={q1,q2,q3,q4}, а состояние q5 формирует другой класс Q'2=q5. При этом выполняются условия Q'1ÈQ'2=Q и Q'1ÇQ'2=Æ.
Построим таблицу переходов пар неотличимых состояний.
Анализ таблицы a) показывает, что для входного символа "0" неотличимые пары (q1; q3) и (q2; q3), подчеркнутые в таблице, переходят в пары (q1; q5) и (q4; q5), состояния которых принадлежат различным классам q1ÎQ'1 и q5ÎQ'2, q4ÎQ'1 и q5ÎQ'2. Поэтому пары (q1; q3), (q2; q3) и (q3; q4) следует удалить из числа претендентов на совместимость (из левого столбца таблицы) и составить таблицу b).
Анализ таблицы b) показывает, что для входного символа "1" неотличимые пары (q1; q2) и (q2; q4) переходят в удаленную на предыдущем этапе неотличимую пару (q2; q3).
Поэтому пары (q1; q2) и (q2; q4) следует удалить из числа претендентов на совместимость (из левого столбца таблицы) и составить таблицу c).
Анализ таблицы с) показывает, что состояния q1 и q4 формируют класс совместимых состояний Q''i={q1, q4}, то есть они эквивалентны и могут быть замещены одним состоянием q1«{q1, q4}.
| таблицы a) | Таблица b) | |||||
| неотл-е сост-я | xÎX | неотл-е сост-я | xÎX | |||
| (q1; q2) | (q1; q1) | (q2; q3) | (q1; q2) | (q1; q1) | (q2; q3) | |
| (q1; q3) | (q1; q5) | (q1; q2) | (q1; q4) | (q1; q4) | (q2; q2) | |
| (q1; q4) | (q1; q4) | (q2; q2) | (q2; q4) | (q1; q4) | (q2; q3) | |
| (q2; q3) | (q1; q5) | (q1; q3) | ||||
| (q2; q4) | (q1; q4) | (q2; q3) | Таблица с) | |||
| (q3; q4) | (q4; q5) | (q1; q2) | неотл-е сост-я | xÎX | ||
| (q1; q4) | (q1; q4) | (q2; q2) |
Если эквивалентные состояния автомата заместить одним состоянием, то получим автомат с меньшим числом состояний. Автомат, среди состояний которого нет эквивалентных, называют минимальным..
| qÎQ | xÎX | |
| q1 | q1; 1 | q2; 0 |
| q2 | q1; 1 | q3; 0 |
| q3 | q5; 1 | q1; 0 |
| q5 | q4; 1 | q3; 1 |
Поиск минимального автомата предусматривает отыскание неотличимых и совместимых состояний, формирование их классов и анализ значений функций переходов y: (QÄX)®Q и выходов j: (QÄX)®Y по представителям этих классов.
|
|
|
Алгоритм минимизации числа внутренних состояний детерминированного автомата:
Пусть функции выходов и переходов детерминированного конечного автомата заданы таблицами 6.18 и 6.19.
| Таблица 6.18 | Таблица 6.19 | |||||||||
| qÎQ | xÎX | qÎQ | xÎX | |||||||
| x1 | x2 | … | xn | x1 | x2 | … | xn | |||
| … | … | … | … | … | … | … | … | … | … | |
| qp | ys | yp | … | yt | qp | qr | qv | … | qt | |
| qr | yi | yj | … | yp | qr | qp | qt | … | qr | |
| qs | yi | yj | … | yp | qs | qt | qp | … | qs | |
| qt | ys | yp | … | yt | qt | qs | qv | … | qp | |
| qu | yi | yj | … | yp | qu | qp | qv | … | qt | |
| qv | ys | yi | … | yp | qv | qs | qv | … | qp | |
| … | … | … | … | … | … | … | … | … | … |
шаг 1: выделить в таблице выходов неотличимые состояния по правилу:
"если среди множества состояний qÎQ найти такие qi и qj, у которых значения функции выходов одинаковы для каждого xkÎX, т. е. j(qi;xk)=j(qj;xk), то состояния qi и qj являются неотличимыми";
в результате анализа всех пар (qi; qj)Î(QÄQ) можно выделить пары неотличимых состояний: (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: составить таблицу переходов пар неотличимых состояний по правилу:
"левый столбец таблицы 6.20 представить парами неотличимых состояний, которые для удобства анализа сгруппировать по классам; позиции таблицы заполнить парами значений функций переходов (y(qi; xk); y(qj; xk)) для каждой неотличимой пары (qi; qj) и для каждого xkÎX по данным таблицы 6.19";
шаг 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) несовместима и ее следует удалить из левого столбца таблицы переходов пар неотличимых состояний; процедуру повторять до тех пор, пока все состояния каждого класса неотличимости не станут совместимыми";
по данным таблицы 6.20 несовместимыми являются состояния пар (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);
Таблица.6.20
| неотличимые состояния (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) |
шаг 5: сформировать на множестве пар совместимых состояний классы совместимых состояний по правилу:
"если среди множества пар совместимых состояний существуют пары (qi; qj), (qj; qk) и (qi; qk), то есть выполняется условие транзитивности для отношения совместимости, то состояния qi, qj, qk формирует класс совместимых состояний Q'i= {qi; qj; qk}”;
анализ классов неотличимых состояний показывает, что класс Q'2 является классом совместимых состояний, а из класса неотличимых состояний Q'1 удалить состояние qu, оформив два класса совместимых состояний Q''1={qs; qr} и Q''2=qu;
шаг 6: если в результате анализа пар неотличимых состояний найдены классы совместимых состояний, то конец иначе перейти к шагу 3;
шаг 7: состояния каждого класса совместимых состояний замеcтить эквивалентным состоянием q'i«{qi;qj}, а несовместимые состояния сохраняют свое значение в описании минимального автомата.
Пример: дан детерминированный автомат M=<X; Y; Q; y; j>, где X={0;1}, Y={0;1}, Q={q1; q2; q3; q4; q5; q6; q7; q8; q9}, а функции y и j заданы таблицей. Найти минимальный автомат.
| текущее состояние | xÎX | ||||
| Анализ состояний детерминированного автомата по значениям функции выхода позволяет определить множество пар неотличимых состояний {(q2; q4), (q2; q5), (q2; q6), (q2; q7), (q2; q8), (q4; q5), (q4; q6)}. По условиям симметричности, рефлексивности и транзитивности формирируется один класс неотличимых состояний Q'4={q2;q4;q5;q6;q7;q8}. Составим таблицу переходов пар неотличимых состояний (cм. таблицу а)). | |||||
| 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 | |||
|
|
|
| Таблица а) | Таблица b) | |||||
| неотл-е сост-я | xÎX | xÎX | ||||
| q2; q4) | (q2; q2) | (q2; q2) | (q2; q4) | (q2; q2) | (q2; q2) | |
| (q2; q5) | (q2; q2) | (q2; q2) | (q2; q5) | (q2; q2) | (q2; q2) | |
| (q2; q6) | (q2; q3) | (q2; q9) | (q2; q7) | (q2; q6) | (q2; q8) | |
| (q2; q7) | (q2; q6) | (q2; q8) | (q4; q5) | (q2; q2) | (q2; q2) | |
| (q2; q8) | (q2; q9) | (q2; q9) | (q4; q7) | (q2; q6) | (q2; q8) | |
| (q4; q5) | (q2; q2) | (q2; q2) | (q5; q7) | (q2; q6) | (q2; q8) | |
| (q4; q6) | (q2; q3) | (q2; q9) | (q6; q8) | (q3; q9) | (q9; q9) | |
| (q4; q7) | (q2; q6) | (q2; q8) | ||||
| (q4; q8) | (q2; q9) | (q2; q9) | Таблица с) | |||
| (q5; q6) | (q2; q3) | (q2; q9) | неотл-е сост-я | xÎX | ||
| (q5; q7) | (q2; q6) | (q2; q8) | ||||
| (q5; q8) | (q2; q9) | (q2; q9) | (q2; q4) | (q2; q2) | (q2; q2) | |
| (q6; q7) | (q3; q6) | (q8; q9) | (q2; q5) | (q2; q2) | (q2; q2) | |
| (q6; q8) | (q3; q9) | (q9; q9) | (q4; q5) | (q2; q2) | (q2; q2) | |
| (q7; q8) | (q6; q9) | (q8; q9) |
Сравним пары значений функций переходов с парами неотличимых состояний левого столбца для каждого символа входного алфавита.
Для символа "1" пары (q2; q9) и (q8; q9) не принадлежат множеству неотличимых состояний. Следовательно, пары неотличимых состояний (q2; q6), (q2; q8), (q4; q6), (q4; q8), (q5; q6), (q5; q8), (q6; q7) и
(q7; q8) не могут претендовать на совместимость. Эти пары в таблице а) подчеркнуты. Их следует удалить из левого столбца, составить новую таблицу переходов (см. таблицу b) и продолжить анализ для других символов входного алфавита.
Для символа "0" пара (q2;q6) принадлежит удаленной паре неотличимости. Следовательно, пары неотличимых состояний (q2; q7) и (q4; q7) и (q5; q7), для которых сформированы пары (q2,q6), также не могут претендовать на совместимость. В таблице b) эти пары подчеркнуты. Кроме того, состояния пары (q3;q9) принадлежат отличимым состояниям. Поэтому пара (q6;q8) также не может претендовать на совместимость. Пары, не претендующие на совместимость, удалить из левого столбца таблицы и составить таблицу с).
Если любая пара функций переходов имеет эквивалент среди неотличимых состояний, то конец иначе повторить процесс удаления пар неотличимых состояний. В данном примере все пары переходов имеют значение (q2; q2). По условию рефлексивности они эквивалентны.
| Таблица d) | |||
| текущее состояние | xÎX | ||
| По условию транзитивности они формируют класс эквивалентных состояний Q''1={q2; q4; q5}. Пусть представителем класса эквивален- ции будет q2«{q2; q4; q5}. Слева дана таблица поведения минимального автомата. | |||
| q1 | q9; 1 | q1; 1 | |
| q2 | q2; 1 | q2; 1 | |
| q3 | q7; 0 | q2; 1 | |
| q6 | q3; 1 | q9; 0 | |
| q7 | q6; 1 | q8; 0 | |
| q8 | q9; 1 | q9; 0 | |
| q9 | q2; 0 | q6; 0 |
Пусть для исходного автомата q1=q0 и a= (010011101100).
вход: 0 - 1 - 0 - 0 - 1 - 1 - 1 - 0 - 1 - 1 - 0 - 0
q: q1 -q9 -q6 - q3 - q7 - q8 - q9 - q6 - q3 -q5 -q2 - q2 - q2
выход: 1 - 0 -1 - 0 - 0 - 0 - 0 - 1 - 1 - 0 -1 - 1,
то есть b=(101000011011).
Пусть для минимального автомата q1=q0 и a= (010011101100).
вход: 0 -1 -0 -0 -1 -1 -1 -0 -1 -1 -0 -0
q: q1 -q9 -q6 -q3 -q7 -q8 -q9 -q6 -q3 -q2 -q2 -q2 -q2
выход: 1 -0 -1 -0 -0 -0 -0 -1 -1 -0 -1 -1,
то есть b= (101000011011).
Так установлена эквивалентность минимального и исходного автоматов Мили.
Пример: для детерминированного автомата M=<X; Y; Q; y; j>, где X={0; 1; 2}, Y={0; 1}, Q={q1; q2; q3; q4; q5; q6; q7; q8; q9}, функции y и j заданы таблицей поведения. Найти минимальный автомат.
| Таблица поведения | ||||||
| Анализ пар (qi; qj)Î(QÄQ) по значениям функции выхода для каждого символа xkÎX позволяет выделить два подмножества неотличимых состояний: Q'1={q1; q3; q5; q7; q8} и Q'2={q2; q4; q6; q9}. Пары неотличимых состояний: (q1; q3); (q1; q5); (q1; q7); (q1; q8); (q3; q5); (q3; q7); (q3; q8); (q5; q7); (q5; q8); (q7; q8); (q2; q4); (q2; q6); (q2; q9); (q4; q6); (q4; q9); (q6; q9). | Текущие состояния | xÎX | ||||
| 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 | |||
Для множества пар неотличимых состояний составим таблицу переходов пар состояний (cм. таблицу а)).
Сравним пары значений функции переходов с парами неотличимых состояний левого столбца для каждого символа входного алфавита.
Для символа "2" состояния пар значений функции переходов (q4; q7), (q2; q7), (q6; q7) принадлежат разным классам неотличимости. Следовательно, пары неотличимых состояний (q2; q9), (q4; q9) и (q6; q9), которые сформировали эти отличимые пары, не могут претендовать на совместимость (в таблице а) эти пары подчеркнуты). Пары, не претендующие на совместимость, следует удалить из левого столбца, составить новую таблицу переходов (см. таблицу b)) и продолжить анализ для других символов входного алфавита.
Для символа "1" состояния пар (q4; q9) и (q2; q9) принадлежат удаленным классам неотличимости. Следовательно, пары неотличимых состояний (q2; q6) и (q4; q6), которые сформировали указанные пары, также не могут претендовать на совместимость (в таблице b) эти пары подчеркнуты). Пары, не претендующие на совместимость, следует удалить из левого столбца, составить новую таблицу переходов (см. таблицу с)) и продолжить анализ для других символов входного алфавита.
Для символа "0" состояния пар (q2; q6) и (q4; q6) принадлежат удаленным классам неотличимости. Следовательно, пары неотличимых состояний (q1; q5), (q1; q7), (q3; q5), (q3; q7), (q5; q8) и (q7; q8), которые сформировали указанные пары, также не могут претендовать на их совместимость (в таблице с) эти пары подчеркнуты). Пары, не претендующие на совместимость, следует удалить из левого столбца, составить новую таблицу переходов (см. таблицу d)) и продолжить анализ для других символов входного алфавита.
| Таблица а) | Таблица b) | |||||||
| Неотл-е сост-я | xÎX | Неотл-е сост-я | xÎX | |||||
| (q1; q3) | (q2; q2) | (q2; q2) | (q5; q5) | (q1; q3) | (q2; q2) | (q2; q2) | (q5; q5) | |
| (q1; q5) | (q2; q6) | (q2; q4) | (q3; q5) | (q1; q5) | (q2; q6) | (q2; q4) | (q3; q5) | |
| (q1; q7) | (q2; q6) | (q2; q2) | (q5; q8) | (q1; q7) | (q2; q6) | (q2; q2) | (q5; q8) | |
| (q1; q8) | (q2; q4) | (q2; q4) | (q5; q7) | (q1; q8) | (q2; q4) | (q2; q4) | (q5; q7) | |
| (q3; q5) | (q2; q6) | (q2; q4) | (q3; q5) | (q3; q5) | (q2; q6) | (q2; q4) | (q3; q5) | |
| (q3; q7) | (q2; q6) | (q2; q2) | (q5; q8) | (q3; q7) | (q2; q6) | (q2; q2) | (q5; q8) | |
| (q3; q8) | (q2; q4) | (q2; q4) | (q5; q7) | (q3; q8) | (q2; q4) | (q2; q4) | (q5; q7) | |
| (q5; q7) | (q6; q6) | (q2; q4) | (q3; q8) | (q5; q7) | (q6; q6) | (q2; q4) | (q3; q8) | |
| (q5; q8) | (q4; q6) | (q4; q4) | (q3; q7) | (q5; q8) | (q4; q6) | (q4; q4) | (q3; q7) | |
| (q7; q8) | (q4; q6) | (q2; q4) | (q7; q8) | (q7; q8) | (q4; q6) | (q2; q4) | (q7; q8) | |
| (q2; q4) | (q1; q3) | (q2; q4) | (q2; q4) | (q2; q4) | (q1; q3) | (q2; q4) | (q2; q4) | |
| (q2; q6) | (q1; q8) | (q4; q9) | (q4; q6) | (q2; q6) | (q1; q8) | (q4; q9) | (q4; q6) | |
| (q2; q9) | (q1; q7) | (q4; q9) | (q4; q7) | (q4; q6) | (q3; q8) | (q2; q9) | (q2; q6) | |
| (q4; q6) | (q3; q8) | (q2; q9) | (q2; q6) | |||||
| (q4; q9) | (q3; q7) | (q8; q9) | (q2; q7) | |||||
| (q6; q9) | (q7; q8) | (q9; q9) | (q6; q7) |
После сравнения пар значений функции переходов с парами неотличимых состояний для каждого символа входного алфавита следует повторить этот шаг алгоритма для контроля несовместимых состояний. Если все пара функции переходов совпадают с парами левого столбца, то конец, иначе повторить процесс для каждого символа входного алфавита.
В данном примере по таблице d) все пары значений функции переходов неотличимы. Следовательно, пары (q1; q3), (q1; q8), (q2; q4), (q3; q8) и (q5; q7) совместимы.
Сформируем классы эквивалентных состояний Q''1={q1; q3; q8}, Q''2={q5; q7}, Q''3={q2; q4} и классы отличимых состояний Q''4=q6 и Q''5=q9. При этом Q''1ÈQ''2ÈQ''3ÈQ''4ÈQ''5=Q и Q''iÇQ''j=Æ.
Для каждого класса эквиваленции выделить одно состояние. Пусть q1 представляет состояния класса Q''1, q5 - Q''2, q2 - Q''3, q6 - Q''4 и q9 - Q''5. Так получен минимальный автомат, поведение которого описано в таблице e).
Для проверки одинаковости работы исходного и минимального автоматов следует подать на их входы произвольную последовательность символов входного алфавита.
| Таблица c | Таблица d | |||||||||
| Неотл-е сост-я | xÎX | Неотл-е сост-я | xÎX | |||||||
| (q1; q3) | (q2; q2) | (q2; q2) | (q5; q5) | (q1; q3) | (q2; q2) | (q2; q2) | (q5; q5) | |||
| (q1; q5) | (q2; q6) | (q2; q4) | (q3; q5) | (q1; q8) | (q2; q4) | (q2; q4) | (q5; q7) | |||
| (q1; q7) | (q2; q6) | (q2; q2) | (q5; q8) | (q2; q4) | (q1; q3) | (q2; q4) | (q2; q4) | |||
| (q1; q8) | (q2; q4) | (q2; q4) | (q5; q7) | (q3; q8) | (q2; q4) | (q2; q4) | (q5; q7) | |||
| (q3; q5) | (q2; q6) | (q2; q4) | (q3; q5) | (q5; q7) | (q6; q6) | (q2; q4) | (q3; q8) | |||
| (q3; q7) | (q2; q6) | (q2; q2) | (q5; q8) | |||||||
| (q3; q8) | (q2; q4) | (q2; q4) | (q5; q7) | |||||||
| (q5; q7) | (q6; q6) | (q2; q4) | (q3; q8) | |||||||
| (q5; q8) | (q4; q6) | (q4; q4) | (q3; q7) | |||||||
| (q7; q8) | (q4; q6) | (q2; q4) | (q7; q8) | |||||||
| (q2; q4) | (q1; q3) | (q2; q4) | (q2; q4) | |||||||
| Таблица e) | ||||||||||
| текущие сост-я | xÎX | |||||||||
| q1 | q2; 1 | q2; 0 | q5; 0 | |||||||
| q2 | q1; 0 | q2; 1 | q2; 1 | |||||||
| q5 | q6; 1 | q2; 0 | q1; 0 | |||||||
| q6 | q1; 0 | q9; 1 | q6; 1 | |||||||
| q9 | q5; 0 | q9; 1 | q5; 1 | |||||||
Пусть для исходного автомата q1=q0 и a= (010200201210).
вход: 0- 1- 0- 2- 0- 0- 2- 0- 1- 2- 1- 0
q: q1- q2- q4- q3- q5- q6- q8- q7- q6- q9- q7- q2- q1
выход: 1- 1- 0- 0- 1- 0- 0- 1- 1- 1- 0- 0,
то есть b=(110010011100).
Для минимального автомата q1=q0 и a= (010200201210).
вход: 0- 1- 0- 2- 0- 0- 2- 0- 1- 2- 1- 0
q: q1- q2- q2- q1- q5- q6- q1- q5- q6- q9- q5- q2- q1
выход: 1- 1- 0- 0- 1- 0- 0- 1- 1- 1- 0- 0,
то есть b=(110010011100).
Так установлена эквивалентность исходного и минимального автоматов.
|
|
|
