Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]


Минимизация конечных автоматов

Минимизация конечных автоматов


Может быть поставлен такой вопрос: нельзя ли для произвольного конечного автомата построить эквивалентный конечный автомат с меньшим числом состояний? Оказывается, что ответ на этот вопрос положителен. Более того, можно построить конечный автомат, эквивалентный исходному и имеющий наименьшее число состояний (среди всех конечных автоматов, эквивалентных ему). Процедуру построения такого автомата называют минимизацией конечного автомата.


В силу теоремы о детерминизации (см. теорему 7.7) можно считать, что исходный конечный автомат M=(V,Q,q_0,F,\delta) является детерминированным.


Будем также предполагать, что в исходном конечном автомате нет состояний, которые не достижимы из начального состояния. Это предположение мотивировано тем, что если в M_0 существуют состояния, не достижимые из начального, то их можно найти (используя, скажем, поиск в ширину на графе M) и удалить со всеми инцидентными им дугами.


На множестве состояний автомата M зададим семейство отношений эквивалентности следующим образом:


1) 0-эквивстентностъ: для произвольных состояний q_1 и q_2 полагаем q_1\equiv^0q_2 тогда и только тогда, когда они оба являются заключительными или оба не являются заключительными;


2) k-эквивалентность: при k\geqslant1 полагаем q_1\equiv^kq_2 тогда и только тогда, когда q_1\equiv^{k-1}q_2, т.е. состояния k_1 и q_2 (k-1)-эквивалентны, и, кроме того, для любого входного символа a состояния \delta(q_1,a) и \delta(q_2,a) также (k-1)-эквивалентны*.


*Напомним, что функция переходов детерминированного конечного автомата определена как отображение \delta\colon\,Q\times V\to Q (см. замечание 7.7).


Смысл отношения k-эквивалентности

Чтобы понять смысл отношения k-эквивалентности, обратимся к рис. 7.23. На этом рисунке q_1 и q_2 — (k-1)-эквивалентные состояния, т.е. они принадлежат одному и тому же классу (k-1)-эквивалентности C_1. Эти состояния, согласно данному выше определению, станут k-эквивалентными, если для любого входного символа a состояния \delta(q_1,a) и \delta(q_2,a) также являются (k-1)-эквивалентными, содержащимися в некотором классе (k-1)-эквивалентности C_2 (возможно, что C_1=C_2). Можно сказать, что (k-1)-эквивалентные состояния будут также и k-эквивалентными, если переход из них по любому входному символу "сохраняет" (k-1)-эквивалентность состояний, т.е. состояния, в которые конечный автомат переходит из (k-1)-эквивалентных состояний, снова окажутся (k-1)-эквивалентными.


Состояния автомата в разных классах (k-1)-эквивалентности

Если же найдется хотя бы один входной символ а, такой, что состояния \delta(q_1,a) и \delta(q_2,a) окажутся в разных классах (к-1)-эквивалентности (рис. 7.24), то состояния q_1 и q_2 уже не будут k-эквивалентными (образно говоря, они разойдутся по разным классам k-эквивалентности, так как переход из них по некоторому символу "разрушает" (k-1)-эквивалентность).


Таким образом, для любого k\geqslant0 отношение эквивалентности \equiv^{k+1} включается в отношение \equiv^{k}, и, следовательно, любой класс (k+1)-эквивалентности включается в некоторый класс k-эквивалентности (точнее, каждый класс k-эквивалентности или разбивается на несколько попарно непересекающихся классов (k+1)-эквивалентности, или, если все его состояния остаются (k+1)-эквивалентными, не изменяется). Это значит, что разбиение множества состояний на классы (k+1)-эквивалентности является, не более "крупным", т.е. содержит не меньше классов эквивалентности, чем разбиение на классы k-эквивалентности.


Минимизация конечного автомата состоит в последовательном "измельчении" разбиения множества Q на классы эквивалентности до тех пор, пока не получится разбиение, которое уже нельзя измельчить (очевидно, что такое разбиение для некоторого k\leqslant n=|Q| всегда существует). Более строго: указанные выше отношения эквивалентности строятся до такого наименьшего k, что отношение \equiv^{k} совпадет с отношением \equiv^{k-1}. Это отношение и определяет самое мелкое разбиение множества состояний. Обозначим его просто \equiv. Тогда минимальный конечный автомат M=(V',Q',q'_0,F',\delta'), т.е. автомат с наименьшим числом состояний, эквивалентный исходному, определяется следующим образом:


\begin{aligned}&V'=V,\quad Q'=Q/_{\equiv},\quad q'_0=[q_0],\quad F'=\{[f]\colon\, f\in F\},\\ &(\forall a\in V)(\forall q\in Q)\delta([q],a)=[\delta(q,a)], \end{aligned}

где через [ q] обозначен класс эквивалентности состояния q по отношению \equiv.


Можно доказать вполне строго (аналогично доказательству корректности алгоритма детерминизации), что конечные автоматы M и M' эквивалентны.


Резюмируем полученные результаты в виде теоремы.


Теорема 7.9. Для произвольного конечного автомата может быть построен эквивалентный ему конечный автомат с наименьшим числом состояний.


Вытекающий из этой теоремы алгоритм минимизации может быть описан так:


1) строим эквивалентный исходному детерминированный конечный автомат;

2) если в полученном конечном автомате остались состояния, не достижимые из начальной вершины, удаляем их (для обнаружения таких вершин может быть использован алгоритм поиска в ширину);

3) к полученному конечному автомату применяем изложенный выше алгоритм построения разбиения множества состояний на классы эквивалентности по отношению \equiv и строим минимальный конечный автомат M', как описано выше.


Замечание 7.11. Если детерминизация конечного автомата проводится методом "вытягивания", то все вершины в детерминированном конечном автомате будут достижимы из начальной вершины.


Кроме того, подчеркнем еще раз, что алгоритм минимизации применяется только к детерминированным конечным автоматам.




Пример 7.11. Минимизируем конечный автомат, изображенный на рис. 7.21.


Введем новые обозначения для состояний автомата:


\begin{aligned}&\{q_0\}=s_0,\quad \{q_0,q_1\}=s_1,\quad \{q_0,q_2\}=s_2,\\ &\{q_0,q_1,q_3\}=s_3,\quad \{q_0,q_2,q_3\}=s_4,\quad \{q_0,q_3\}=s_5. \end{aligned}

Полученный автомат изображен на рис. 7.25.


Минимальный конечный автомат

Запишем разбиение множества состояний автомата для отношения \equiv^{0}\colon\, \{s_0,s_1,s_2\},\,\{s_3,s_4,s_5\}.


Так как состояния \delta(s_2,0)=s_0 и \delta(s_2,1)=s_3 не являются 0-эквивалентными состояниями, то в разбиении для 1-эквивалентности они "разойдутся" по разным классам; разбиение, определяемое отношением \equiv^1, будет иметь вид


\{s_0,s_1\},\qquad \{s_2\},\qquad \{s_3,s_4,s_5\}.

Далее, при переходе к 2-эквивалентности придется "развести" состояния s_0 и s_1. Поскольку для всех состояний из множества \{s_3,s_4,s_5\} конечный автомат переходит в одно из этих же состояний, то разбиение на классы 2-эквивалентности и есть искомое "мельчайшее" разбиение:


\{s_0\},\qquad \{s_1\},\qquad \{s_2\},\qquad \{s_3,s_4,s_5\}.

На рис. 7.26 приведен граф минимального конечного автомата.


Граф минимального конечного автомата



Предельные случаи процедуры минимизации конечных автоматов


Заметим, что применение рассмотренной процедуры минимизации может дать два крайних случая:


Эквивалентные состояния конечного автомата

1) все состояния исходного конечного автомата окажутся эквивалентными и тогда в минимальном конечном автомате останется только одно состояние;

2) итоговое разбиение будет состоять из одноэлементных классов эквивалентности — это означает, что исходный конечный автомат нельзя минимизировать, он уже минимален.


Первый случай проиллюстрирован на рис. 7.27. Здесь приведено построение и минимизация конечного автомата, допускающего язык, обозначенный регулярным выражением (a^{\ast}b^{\ast})^{\ast}.


После удаления λ-переходов получается детерминированный автомат, все состояния которого заключительные. Значит, минимальный автомат состоит из одной вершины и допускает язык (a+b)^{\ast}. Тем самым мы еще и доказали эквивалентность регулярных выражений (a+b)^{\ast} и (a^{\ast}b^{\ast})^{\ast} (в алфавите \{a,b\}).


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


Если мы хотим выяснить, эквивалентны ли автоматы M_1 и M_2, то можно минимизировать каждый из них. Если минимальные автоматы M'_1 и M'_2 имеют множества состояний с разным числом вершин, то исходные автоматы заведомо не эквивалентны. Можно доказать, что исходные автоматы эквивалентны тогда и только тогда, когда соответствующие им минимальные автоматы M'_1 и M'_2 изоморфны. Конечные автоматы M'_1 и M'_2 считаются изоморфными, если существует такая биекция h множества состояний первого автомата на множество состояний второго, которая является изоморфизмом данных конечных автоматов как ориентированных графов и обладает дополнительно следующими свойствами:


1) если q_{01} — начальное состояние конечного автомата M'_1, то h(q_{01})=q_{02} — начальное состояние конечного автомата M'_2;

2) если F_1 — подмножество заключительных состояний конечного автомата M'_1, то h(F_1)=F_2 — подмножество заключительных состояний конечного автомата M'_2;

3) для любых двух состояний q и r конечного автомата M'_1 и любого входного символа a имеем q\to_{a}r тогда и только тогда, когда h(q)\to_{a}h(r).


В общем случае проблема распознавания эквивалентности M_1 и M_2 сводится к проблеме распознавания изоморфизма минимальных автоматов. Для малого числа вершин (до 10) этот изоморфизм, как правило, распознается "невооруженным глазом", но в общем случае нужны специальные алгоритмы.

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved