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

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

Пусть функции выходов и переходов детерминированного конечного автомата заданы таблицами 1.27 и 1.28.

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

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

"если среди множества состояний qÎQ найти такие q_i и q_j, у которых значения функции выходов одинаковы для каждого символа входного алфавита x_kÎX, т. е. j(q_i;x_k)=j(q_j;x_k), то состояния q_i и q_j являются неотличимыми";

в результате анализа всех пар (q_i;q_j)Î(QÄQ) по таблице 1.27 можно выделить пары неотличимых состояний:(q_p;q_t), (q_r;q_s), (q_r;qu), (q_s;q_u);

шаг 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}";

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

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

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

Таблица 1.29.

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

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

по данным таблицы 1.29 несовместимыми являются состояния пары (q_r;q_u) и (q_s;q_u) класса Q'₁, так как для x₂ значения функций переходов принадлежат различным классам: (y(q_r;x₂)=q_tÎQ'₂; y(q_u;x₂)=q_vÎQ'₃) и (y(q_s;x₂)=q_pÎQ'₂; y(q_u;x₂)=q_vÎQ'₃), а состояния пары (q_r;q_s) класса Q'₁ являются совместимыми, так как значения функций переходов для каждого символа входного алфавита принадлежат одному классу (y(q_r;x₁)=q_pÎQ'₂;y(q_s;x₁)=q_tÎQ'₂), (y(q_r;x₂)=q_tÎQ'₂;y(q_s;x₂)=q_pÎQ'₂),... и (y(q_r;x_n)=q_rÎQ'₁;y(q_s;x_n)=q_sÎQ'₁);

шаг 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}”;

анализ классов неотличимых состояний показывает, что класс Q'₂ является классом совместимых состояний, а из класса неотличимых состояний Q'₁ cледует удалить состояние q_u, оформив два класса совместимых состояний Q''₁={q_s;q_r} и Q''₂=q_u;

шаг 6: если в результате анализа всех пар неотличимых состояний для каждого символа входного алфавита x_kÎX найдены классы совместимых и несовместимых состояний, то конец иначе перейти к шагу 3;

шаг 7: состояния каждого класса совместимых состояний замещаются эквивалентным состоянием q'_i«{q_i;q_j}, а несовместимые и отличимые состояния сохраняют свое значение в описании минимального автомата.

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

Таблица 1.30.

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

Таблица 1.31.

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

Анализ множества состояний детерминированного автомата по значениям функции выхода для каждого символа входного алфавита x_kÎX позволяет выделить четыре класса: 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₇); (q₅;q₈); (q₆;q₇); (q₆;q₈); (q₇;q₈). По этому множеству составим таблицу переходов пар состояний (cм. таблицу 1.32).

Поскольку отношение эквиваленции симметрично, т.е. (q_i;q_j)«(q_j;q_i), то в таблице для удобства анализа всюду левый полюс пары состояний имеет меньший индекс, чем правый. Так как отношение эквиваленции рефлексивно, то пару (q_i;q_i) в таблице переходов следует считать неотличимой и совместимой. Сравним по таблице 1.32 пары значений функции переходов с парами неотличимых состояний левого столбца для каждого символа входного алфавита.

Для символа "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₈), для которых сформированы пары значений функции переходов (q₂;q₉) (q₈;q₉), не могут претендовать на совместимость.

Таблица 1.32.

В таблице 1.32 эти пары выделены подчеркиванием. Пары, не претендующие на совместимость, следует удалить из левого столбца, составить новую таблицу переходов (см. таблицу 1.33) и продолжить анализ для других символов входного алфавита.

Таблица 1.33.

Для символа "0" пара (q₂;q₆) принадлежит удаленной паре класса неотличимости. Следовательно, пары неотличимых состояний (q₂;q₇) и (q₄;q₇) и (q₅;q₇), для которых сформированы пары (q₂,q₆), также не могут претендовать на их совместимость. В таблице 1.33 эти пары выделены подчеркиванием. Кроме того, состояния пары (q₃;q₉) также принадлежат различным классам (q₃ÎQ'2;q₉ÎQ'₃). Поэтому пару неотличимых состояний левого столбца (q₆;q₈) также следует удалить из таблицы. В таблице 1.33 эти пары выделены подчеркиванием. Пары, не претендующие на совместимость, следует удалить из левого столбца таблицы и составить таблицу 1.34.

Таблица 1.33.

После сравнения пар значений функции переходов с парами неотличимых состояний для каждого символа входного алфавита следует повторить этот шаг алгоритма для контроля несовместимых состояний. Если любая пара значений функции переходов имеет эквивалент среди множества неотличимых состояний, то конец иначе повторить процесс удаления пар неотличимых состояний. В данном примере все пары значений функции переходов имеют единое значение (q₂;q₂). Следовательно, пары (q₂;q₄), (q₂;q₅) и (q₄;q₅) неотличимы и совместимы, т.е они формируют класс эквивалентных состояний Q''₁={q₂;q₄;q₅}. Остальные состояния исходного автомата не претендуют на эквивалентность. Пусть представителем класса эквиваленции Q''₁ будет состояние q₂.

Для описания минимального автомата составим таблицу поведения (таблица 1.35), таблицу соединения (таблица 1.36) и нарисуем граф (рис. 1.16).

Таблица 1.35.

Таблица 1.36.

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

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

Пусть для исходного автомата q₁=q₀ и a= (010011101100), тогда

вход: 0 - 1 - 0 - 0 - 1 - 1 - 1 - 0 - 1 - 1 - 0 - 0

q: q₁ - q₉ - q₆ - q₃ - q₇ - q₈ - q₉ - q₆ - q₃ - q₅ - q₂ - q₂ - q₂

выход: 1 - 0 - 1 - 0 - 0 - 0 - 0 - 1 - 1 - 0 - 1 - 1,

то есть b= (101000011011).

Пусть для минимального автомата q₁=q₀ и a= (010011101100), тогда

вход: 0 - 1 - 0 - 0 - 1 - 1 - 1 - 0 - 1 - 1 - 0 - 0

q: q₁ - q₉ - q₆ - q₃ - q₇ - q₈ - q₉ - q₆ - q₃ - q₂ - q₂ - q₂ - q₂

выход: 1 - 0 - 1 - 0 - 0 - 0 - 0 - 1 - 1 - 0 - 1 - 1,

то есть b= (101000011011).

Так установлена эквивалентность минимального и исходного автоматов Мили.

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

Таблица 1.37.

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

Таблица 1.38.

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

Анализ множества пар (q_i;q_j)Î(QÄQ) по значениям функции выхода для каждого символа входного алфавита x_kÎX позволяет выделить два подмножества неотличимых состояний: Q'₁={q₁;q₃;q₅;q₇;q₈} и Q'₂={q₂;q₄;q₆;q₉}. Таблицами 1.39 и 1.40 представлены таблицы поведения для классов неотличимых состояний.

Пары неотличимых состояний: (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₆;q9). Для множества пар неотличимых состояний составим таблицу переходов пар состояний (cм. таблицу 1.41).

Таблица 1.41.

Сравним пары значений функции переходов с парами неотличимых состояний левого столбца для каждого символа входного алфавита. Для символа входного алфавита "2" состояния пар значений функции переходов (q₄;q₇), (q₂;q₇), (q₆;q₇) принадлежат разным классам неотличимости: q₂, q₄, q₆ÎQ'₂, а q₇ÎQ'₁. Поэтому в левом столбце нет соответствующих пар неотличимости. Следовательно, пары неотличимых состояний (q₂;q₉), (q₄;q₉) и (q₆;q₉), для которых сформированы пары значений функции переходов, не могут претендовать на их совместимость. В таблице 1.41 эти пары выделены подчеркиванием. Пары, не претендующие на совместимость, следует удалить из левого столбца, составить новую таблицу переходов (см. таблицу 1.42) и продолжить анализ для других символов входного алфавита.

Таблица 1.42.

Для символа входного алфавита "1" состояния пар значений функции переходов (q₄;q₉), (q₂;q₉) принадлежат удаленным классам неотличимости. Следовательно, пары неотличимых состояний (q₂;q₆) и (q₄;q₆), для которых сформированы указанные пары значений функции переходов, также не могут претендовать на их совместимость. В таблице 1.42 эти пары выделены подчеркиванием. Пары, не претендующие на совместимость, следует удалить из левого столбца, составить новую таблицу переходов (см. таблицу 1.43) и продолжить анализ для других символов входного алфавита.

Для символа входного алфавита "0" состояния пар значений функции переходов (q₂;q₆), (q₄;q₆) принадлежат удаленным классам неотличимости. Следовательно, пары неотличимых состояний (q₁;q₅), (q₁;q₇), (q₃;q₅), (q₃;q₇), (q₅;q₈) и (q₇;q₈), для которых сформированы указанные пары значений функции переходов, также не могут претендовать на их совместимость. В таблице 1.43 эти пары выделены подчеркиванием. Пары, не претендующие на совместимость, следует удалить из левого столбца, составить новую таблицу переходов (см. таблицу 1.44) и продолжить анализ для других символов входного алфавита.

После сравнения пар значений функции переходов с парами неотличимых состояний для каждого символа входного алфавита следует повторить этот шаг алгоритма для контроля несовместимых состояний.

Таблица 1.43.

Таблица 1.44.

Если все пара значений функции переходов тождественны парам среди множества пар неотличимых состояний, то конец иначе повторить процесс удаления пар неотличимых состояний. В данном примере по таблице 1.44 все пары значений функции переходов имеют тождественную пару среди множества неотличимых состояний в левом столбце таблицы, либо имеют общее значение (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''_iÇQ''_j= Æ для i,j=1,2,3,4,5 при условии i¹j.

Для каждого класса эквиваленции нужно выделить одно состояние. Пусть состояние q₁ представляет класс Q''₁, q₅ - Q''₂, q₂ - Q''₃ , q₆ - Q''₄ и q₉ - Q''₅.

Так получен минимальный автомат, эквивалентный исходному, множество внутренних состояний которого есть Q'={q₁;q₂;q₅;q₆;q₉}. Поведение минимального автомата описано таблицей 1.45. Таблица 1.46 описывает соединения состояний автомата, а рис. 1.18 - его граф.

Таблица 1.45.

Таблица 1.46.

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

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

Пусть для исходного автомата q₁=q₀ и a= (010200201210), тогда

вход: 0 - 1 - 0 - 2 - 0 - 0 - 2 - 0 - 1 - 2 - 1 - 0

q: q₁ - q₂ - q₄ - q₃ - q₅ - q₆ - q₈ - q₇ - q₆ - q₉ - q₇ - q₂ - q₁

выход: 1 - 1 - 0 - 0 - 1 - 0 - 0 - 1 - 1 - 1 - 0 - 0

то есть b= (110010011100).

Пусть для минимального автомата q₁=q₀ и a=(010200201210), тогда

вход: 0 - 1 - 0 - 2 - 0 - 0 - 2 - 0 - 1 - 2 - 1 - 0

q: q₁ - q₂ - q₂ - q₁ - q₅ - q₆ - q₁ - q₅ - q₆ - q₉ - q₅ - q₂ - q₁

выход: 1 - 1 - 0 - 0 - 1 - 0 - 0 - 1 - 1 - 1 - 0 - 0

то есть b= (110010011100).

Так установлена эквивалентность минимального и исходного автоматов.

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

1) Каковы правила формирования классов неотличимых состояний?

2) Каковы правила формирования совместимых состояний?

3) Какими свойствами обладает отношение эквиваленции?

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

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

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

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

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

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