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

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

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

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

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


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

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


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


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


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


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


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


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


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


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

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


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

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


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


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


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

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


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


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


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


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


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

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

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


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


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




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


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


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

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


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

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


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


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

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


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

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


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



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


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


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

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

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


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


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


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


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


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

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

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


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


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


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

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