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

Поиск минимального недетерминированного автомата усложняется тем, что в таблицах переходов и выходов есть неопределенные позиции. Однако, анализ функций переходов y:(QÄX)®Q и выходов j:(QÄX)®Y позволяет находить неотличимые и совместимые состояния даже при наличии неопределенных позиций, а последующее согласование совместимых классов - находить эквивалентные состояния. Пусть функции выходов и переходов недетерминированного автомата заданы таблицами 1.47 и 1.48.

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

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

"а) если среди множества пар состояний автомата (q_i;q_j)Î(QÄQ) можно найти такие q_i и q_j, для которых значения функций выходов j(q_i;x_k) и j(q_j;x_k) определены для x_kÎX и они совпадают, то есть j(q_i;x_k)=j(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, для которых значения функции выходов j(q_i;x_k) и j(q_j;x_k) различны хотя бы для одного x_kÎX, т. е. j(q_i;x_k)¹j(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 по таблице переходов парами значений (y(q_i;x_k);y(q_j;x_k)); если хотя бы одно из значений функции переходов y(q_i;x_k) или y(q_j;x_k) имеет значение "_*", то паре (y(q_i;x_k);y(q_j;x_k)) присвоить также значение "_*""; (смотри таблицу 1.49);

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

"если для пары неотличимых состояний (q_i;q_j) значения функции переходов (y(q_i;x_k);y(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 значения функций переходов y(q_i;x_k) и y(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;y;jñ, где X={x₁;x₂;x₃;x₄}, Y={0;1}, Q={q₁;q₂;q₃;q₄;q₅}, функции y и j заданы таблицей поведения (см. таблицу 1.53) . Найти минимальный автомат.

Таблица 1.53.

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

Таблица 1.54.

Согласно алгоритма имеем множество неотличимых пар: (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.

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

Таблица 1.56.

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

Таблица 1.57.

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

Таблица 1.58.

Анализ таблицы 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.

Таблица 1.60.

Таблица 1.61.

Таблица 1.62.

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

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

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

а) пусть a= (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 - _*;

то есть b=(011_*); то есть b=(011_*);

b) пусть a=(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 - _*;

то есть b=(_*01_*); то есть b=(_*01_*);

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

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

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

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

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

то есть b=(01_*); то есть b=(01_*);

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

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

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

а)пусть a= (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 - _*;

то есть b=(011_*); то есть b=(011_*);

b)пусть a=(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 - _*;

то есть b=(_*01_*); то есть b=(_*01_*);

Таблица 1.63.

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

Таблица 1.64.

Рис. 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.

Таблица 1.66.

Таблица 1.67.

Таблица 1.68.

Таблица 1.69.

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

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

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

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

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

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

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

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

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

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

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

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

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

Дата добавления: 2015-07-26; просмотров: 254; Нарушение авторских прав

Мы поможем в написании ваших работ!