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

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

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

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

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

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

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

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


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

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


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

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

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

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

[cbm]\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}[/cbm]

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

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

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

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

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

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

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

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

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

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


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

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

[cbm]\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}[/cbm]

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

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

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

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

[cbm]\{s_0,s_1\},\qquad \{s_2\},\qquad \{s_3,s_4,s_5\}.[/cbm]

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

[cbm]\{s_0\},\qquad \{s_1\},\qquad \{s_2\},\qquad \{s_3,s_4,s_5\}.[/cbm]

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

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


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

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


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

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

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

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

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

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

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

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

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

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

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

Источник

Поделитесь с другими:

Если материал понравился Вам и оказался для Вас полезным, поделитесь им со своими друзьями!

Читать по теме:

Интересные статьи: