ДКА минимизација

Под ДКА минимизацијом се подразумева налажење детерминистичког коначног аутомата (ДКА) са најмањим бројем стања који препознаје исти регуларан језик као и задати ДКА. Показује се да је овај аутомат јединствен до на изоморфизам! Наиме, за два ДКА ${\mathcal {A}}=(\Sigma ,Q,i,F,\delta )$ и ${\mathcal {B}}=(\Sigma ,Q',i',F',\delta {}')$ кажемо да су изоморфни уколико постоји бијекција $f:Q\to Q'$ тако да је задовољено :

1. $f(i)=i'$
2. $f[F]=F'$
3. $(\forall a\in \Sigma ,p\in Q)(\,f(\delta (p,a))=\delta '(f(p),a)\,)$

Неформално говорећи, ово заправо значи да ако имамо исцртан мултиграф којим је представљен аутомат ${\mathcal {A}}$, можемо преименовати стања тог графа (остављајући гране нетакнутим и не уводећи нова почетна нити завршна стања ) тако да се добије мултиграф аутомата ${\mathcal {B}}$. Дакле при минимизацији не можемо добити суштински различите аутомате и тиме се решава питање јединствености. У даљем излагању користићемо местимично и проиширену функцију прелаза $\delta ^{*}(p,\omega )$
где $p\in Q,\,\omega \in \Sigma ^{*}$, која се дефинише овако:

• $\delta ^{*}(p,a)=\delta (p,a)$ када $a\in \Sigma$
• $\delta ^{*}(p,\epsilon )=p$
• $\delta ^{*}(p,\omega a)=\delta (\delta ^{*}(p,\omega ),a)$ где је $\omega$ нека реч: $|w|\geq 1$ и $a\in \Sigma$

У наредним секцијама биће изложен скелет теорије која се тиче минималног аутомата, а затим ће бити изложено неколико алгоритама за конструкцију МДКА уз детаљна објашњења.

Минимални аутомат преко левих количника

Нека је дат ДКА ${\mathcal {A}}=(\Sigma ,Q,i,F,\delta )$ који препознаје језик $L$, тј. $L={\mathcal {L}}({\mathcal {A}}).$
Претпоставићемо да овај аутомат нема недоступних стања, јер у супротном елиминацијом комплетног подграфа који је индукован недоступним стањима аутомата добијамо опет ДКА, који је еквивалентан полазном, а има мање стања. Ова претпоставка дакле не умањује општост.

1. За $u\in \Sigma ^{*}$ дефинишемо $u^{-1}X=\{w\in \Sigma ^{*}:uw\in X\}$ где $X\subset \Sigma ^{*}$(Леви количник скупа $X$ по речи $u$)
2. Дефинишемо и за свако $p\in Q\,\,$: ${\mathcal {L}}_{p}({\mathcal {A}})=\{\omega \in \Sigma ^{*}:\delta ^{*}(p,\omega )\in F\}$

Ако означимо $Q(L)=\{u^{-1}L:u\in \Sigma ^{*}\}$ може се показати да је $Q(L)=\{{\mathcal {L}}_{p}({\mathcal {A}}):p\in Q\}$, што заправо повлачи да је $Q(L)$ коначан и да је
$|Q(L)|\leq |Q|$ (*)
Сада можемо да конструишемо ДКА ${\mathcal {B}}=(\Sigma ,Q(L),L,F(L),{\overline {\delta }})$ на следећи начин:

• $F(L)=\{u^{-1}L:u\in L\}$
• ${\overline {\delta }}(Y,a)=a^{-1}Y$

Лако се може показати индукцијом по дужини речи $\omega$ да је ${\overline {\delta }}^{*}$ добро дефинисана функција и да је ${\overline {\delta }}^{*}(Y,\omega )=\omega ^{-1}Y$, а одатле следи ${\mathcal {L}}({\mathcal {A}})={\mathcal {L}}({\mathcal {B}})$, а то није све, на основу (*) закључујемо да је овај аутомат заправо ДКА са минималним бројем стања који је еквивалентан са ${\mathcal {A}}$, у смислу да не постоји ниједан други аутомат са тим својством који има мање стања.

Количнички аутомат и Неродова еквиваленција

Нека је ${\mathcal {A}}=(\Sigma ,Q,i,F,\delta )$ ДКА у коме су сва стања доступна. Увешћемо ознаку $L_{p}={\mathcal {L_{p}({\mathcal {A}})}}$ ради краћег записа. Неородова релација еквиваленције над $Q$
се дефинише на следећи начин:

• $p\sim q\Leftrightarrow L_{p}=L_{q}$

За два стања која су у у овој релацији кажемо да су неразликујућа, у супротном она су разликујућа. Једно важно својство Неродове релације која се експлоатише у неким алгоритмима минимизације ДКА јесте десна инваријантност тј.

• $p\sim q\Leftrightarrow (\forall u\in \Sigma ^{*})(\delta ^{*}(p,u)\sim \delta ^{*}(q,u))$.

Обележићемо са $[p]$ релацију еквиваленције елемента $p\in Q$, количнички скуп са $Q/\sim$.

• Количнички аутомат над ${\mathcal {A}}$ је ДКА ${\mathcal {A}}/\sim =(\Sigma ,Q/\sim ,[i],\{[f]|f\in F\},{\stackrel {\sim }{\delta }})$

за који важи:${\stackrel {\sim }{\delta }}([p],a)=[\delta (p,a)]$.
Може се доказати свака класа Неродове еквиваленције садржи или само завршна, или само незавршна стања, као и да је овај (количнички) аутомат еквивалентан полазном. Количнички аутомат над аутоматом ${\mathcal {A}}$ има исто толико стања као и минимални аутомат описан у претходној секцији што значи да је он такође један минимални аутомат за ${\mathcal {A}}$. Са друга стране, може се показати да уколико је Неродова релација у ствари једнакост над неким ДКА ${\mathcal {B}}$, онда је тај аутомат изоморфан са минималним аутоматом описаним у претходној секцији. Коначни закључак је да су свака два минимална аутомата за задати ДКА међусобно изоморфна, што значи да је при минимизацији довољно одредити само један, а обично је то управо количнички аутомат.

Хопкрофтов алгоритам минимизације

Овај алгоритам као и многи други алгоритми минимизације се своди на одређивање количничког аутомата за неки ДКА ${\mathcal {A}}$, односно одређивање класа еквиваленције Неродове релације. Идеја Хопкрофтовог алгоритма, је да најпре кренемо од неког партиционисања ${\mathcal {P}}$ скупа стања , тако да је свака партиција $P\in {\mathcal {P}}$ у ствари унија класа еквиваленција Неродове релације. (*)
Пошто свако партиционисање скупа одређује једну релацију еквиваленције и обрнуто ( два елемента су у тој релацији акко су у истој партицији) овај услов би могао да се искаже другачије, тј. можемо да кажемо да у ствари желимо да кренемо од неке друге релације еквиваленције, за коју знамо да је надскуп Неродове релације, јер то значи да је количнички скуп те релације у ствари једно партиционисање скупа стања, и свака класа те релације је ништа друго него унија неких Неродових класа еквиваленције. Дакле, најпре дефинишемо неко партиционисање (релацију) које задовољава овај услов, (а оно представља грубу апроксимацију Неродове релације), а затим корак по корак долазимо до све финијих партиција тј. до бољих апроксимација, све док не добијемо количнички скуп за Неродову релацију еквиваленције, у случају овог алгоритма видећемо да је то када не будемо више могли да „произведемо” нове партиције. Дакле услов (*) се пропагира у сваком кораку алгоритма. Пре самог псеудокода, пар разјашњења и дефиниција која се тичу овог алгоритма:

• За дати ДКА увек можемо да пронађемо почетно партиционисање, на пример $\{Q\backslash F,F\}$, будући да свака Неродова класа садржи само завршна или само незавршна стања, лако се види због чега ово задовољава услов (*). Случај када је $F=\emptyset$ је тривијалан, јер тада количнички аутомат има само једно стање ! Ту је дакле посао завршен на почетку па ћемо надаље претпоставити да ово неће да се деси.
• Ако имамо партицију ${\mathcal {P}}$ и $Y,Z\in {\mathcal {P}}$ и $c\in \Sigma$ онда ћемо рећи да $Z$ „сече” партицију $Y$ по слову $c$ уколико постоји неко стање $p\in Y$ тако да $\delta (p,c)\in Z$ и такође постоји $p\in Y$ тако да $\delta (p,c)\not \in Z$, дакле ако означимо $X=\{p\in Q:\delta (p,c)\in Z\}$ ово претходни услови могу да се обједине у $Y\backslash X\neq \emptyset \wedge X\cap Y\neq \emptyset$.
• Уколико постоји партиција $Z$ која сече неку партицију $Y$ по неком слову $c$ онда због тога што је Неродова еквиваленција инваријантна надесно, закључујемо да се скуп $Y$ може заменити двема мањим партицијама $Y\backslash X$ и $X\cap Y$ где је је скуп $X$ дефинисан као у горњој ставци, при чему се не нарушава услов (*).
• Уколико не постоји партиција која сече неку другу партицију (или саму себе) по неком слову, онда то значи да смо дошли до циља, односно ово партиционисање је количнички скуп за Неродову релацију.
• Да не бисмо вршили проверу по свакој партицији тј. да ли она сече неку партицију из текућег партиционисања, формирамо радну лист $W$ која садржи само оне партиције које је нужно проверити и ажурирамо је кроз алгоритам.

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

P := {F, Q \ F};
W := {F};
while (W is not empty) do
     choose and remove a set A from W
     for each c in Σ do
          let X be the set of states for which a transition on c leads to a state in A
          for each set Y in P for which X ∩ Y is nonempty and Y \ X is nonempty do
               replace Y in P by the two sets X ∩ Y and Y \ X
               if Y is in W
                    replace Y in W by the same two sets
               else
                    if |X ∩ Y| <= |Y \ X|
                         add X ∩ Y to W
                    else
                         add Y \ X to W
          end;
     end;
end;

Доказ коректности алгоритма се базира на следећим тврђењима (циљна партиција је она која се не може даље делити, тј. она је једна класа еквиваленције Неродове релације )

• Тврђење 1 : за ${\mathcal {P}}=\{F,Q\backslash F\}$ и $W=\{F\}$ (односно $W=\{Q\backslash F\}$ ) важи $(\forall P\in {\mathcal {P}})$ ($P$ није циљна партиција $\Leftrightarrow$ партиција $F$ (односно $Q\backslash F$) сече $P$ по неком слову.

У сваком кораку алгоритма, имаћемо партицију $P$ и радну листу $W$ и кључан је услов да уколико нека партиција није циљна, онда њу обавезно сече нека партиција из $W$ по неком слову. Овај услов такође мора да се пропагира кроз алгоритам, а претходно тврђење заправо казује да је он испуњен у првом кораку алгоритма. Овај услов ћемо обележити са (**).

• Тврђење 2: Нека партиционисање ${\mathcal {P}}$ и скуп $W\subset {\mathcal {P}}$ задовољавају услов (**). I нека је $A\in W$. Тада уколико:

1. $A$ не сече ниједну партицију из ${\mathcal {P}}$, онда нова радна листа $W'=W\backslash \{A\}$ и партиционисање ${\mathcal {P}}$ задовољавају услов (**).
2. $A$ сече неку партицију $Y\not \in W$ по слову $c$ и разлаже је на две нове партиције $Y',\,Y''$ онда ново партиционисање ${\mathcal {P'}}$ које се добија уклањањем $Y$ и додавањем две нове партиције $Y',\,Y''$ и нова радна листа $W'$ која се добија додавањем тачно једне од нових партиција (било која) задовољавају услов (**)
3. $A$ сече неку партицију $Y\in W$ по слову $c$ и разлаже је на две нове партиције $Y',\,Y''$ онда ново партиционисање ${\mathcal {P'}}$ које се добија уклањањем $Y$ и додавањем две нове партиције $Y',\,Y''$ и нова радна листа $W'=(W\cup \{Y',Y''\})\backslash \{Y\}$ задовољавају услов (**).

Ово је најбржи алгоритам, за минимизацију аутомата који је до сада познат! Његова временска сложеност, узимајући да је величина азбуке константна је ${\mathcal {O}}(|Q|\cdot log|Q|)$. Илуструјмо овај алгоритам на једном примеру.

Пример: Нека је $\Sigma =\{0,1\},\,Q=\{a,b,c,d,e,f\},i=a,F=\{c,d,e\}$ и функција прелаза $\delta$ дата следећом таблицом:

$\delta$	$a$	$b$	$c$	$d$	$e$	$f$
0	$b$	$a$	$e$	$e$	$e$	$f$
1	$c$	$d$	$f$	$f$	$f$	$f$

, Дакле аутомат ${\mathcal {A}}=(\Sigma ,Q,i,F,\delta )$ изгледа овако:

Детерминистички коначни аутомат којег треба минимализовати

1. У почетном кораку иницијализујемо почетно партиционисање ${\mathcal {P}}=\{P_{1},P_{2}\}$ где је $P_{1}=\{a,b,f\},P_{2}=\{c,d,e\}$ и радну листу $W=\{P_{2}\}$.
2. Узимамо неку партицију из $W$ (то је за сада $P_{2}$ ) и одређујемо скуп свих стања са којима се преко 0 долази у ту партицији и скуп свих стања са којима се преко 1 долази у ту партицију респективно: $X(P_{2},0)=P_{2}$, $X(P_{2},1)=\{a,b\}$
3. Одавде видимо да $P_{2}$ преко 0 не сече ни једну партицију, а преко 1 раздваја $P_{1}$ у две нове партиције$\{a,b\}$ и $\{f\}$, додајемо неку од ове две партиције (због оптимизације алгоритма, ону мању) у $W$ истовремено уклањајући $P_{2}$ јер она више неће сећи ниједну партицију. Ново партиционисање је сада ${\mathcal {P'}}=\{P_{1}',P_{2}',P_{3}'\}$ где је $P_{1}'=\{a,b\},\,P_{2}'=\{f\},P_{3}'=\{c,d,e\}$ а нова радна листа је $W'=\{P_{2}'\}$.
4. Сада разматрамо $P_{2}'$ : $X(P_{2}',0)=\{f\},\,\,X(P_{2}',1)=\{c,d,e,f\}$, а одавде видимо да $P_{2}'$ не сече ни једну партицију ни преко 0 а ни преко 1 а како немамо других елемената у $W'$ овде се алгоритам завршава и добили смо тражени количнички скуп.

Дакле количнички (минимални) аутомат изгледа овако:

Минимализовани ДКА

Литература

• Ахо, Алфред V.; Хопцрофт, Јохн Е.; Уллман, Јеффреy D. (1974), „4.13 Партитионинг”, Тхе Десигн анд Аналyсис оф Цомпутер Алгоритхмс, Аддисон-Wеслеy, стр. 157—162 .
• Берстел, Јеан; Боассон, Луц; Цартон, Оливиер; Фагнот, Исабелле (2010), „Минимизатион оф Аутомата”, Аутомата: фром Матхематицс то Апплицатионс, Еуропеан Матхематицал Социетy, арXив:1010.5318  
• Брзозоwски, Ј. А. (1963), „Цаноницал регулар еxпрессионс анд минимал стате грапхс фор дефините евентс”, Проц. Сyмпос. Матх. Тхеорy оф Аутомата (Неw Yорк, 1962), Полyтецхниц Пресс оф Полyтецхниц Инст. оф Брооклyн, Брооклyн, Н.Y., стр. 529—561, МР 0175719 .
• Цâмпеану, Цезар; Цулик, Карел, II; Саломаа, Каи; Yу, Схенг (2001), „Стате Цомплеxитy оф Басиц Оператионс он Фините Лангуагес”, 4тх Интернатионал Wорксхоп он Аутомата Имплементатион (WИА '99), Лецтуре Нотес ин Цомпутер Сциенце, 2214, Спрингер-Верлаг, стр. 60—70, дои:10.1007/3-540-45526-4_6 .
• Давид, Јулиен (2012), „Авераге цомплеxитy оф Мооре’с анд Хопцрофт’с алгоритхмс”, Тхеоретицал Цомпутер Сциенце, 417: 50—65, дои:10.1016/ј.тцс.2011.10.011 .
• Хопцрофт, Јохн (1971), „Ан н лог н алгоритхм фор минимизинг статес ин а фините аутоматон”, Тхеорy оф мацхинес анд цомпутатионс (Проц. Интернат. Сyмпос., Тецхнион, Хаифа, 1971), Неw Yорк: Ацадемиц Пресс, стр. 189—196, МР 0403320 . Сее алсо прелиминарy версион, Тецхницал Репорт СТАН-ЦС-71-190, Станфорд Университy, Цомпутер Сциенце Департмент, Јануарy 1971.
• Хопцрофт, Јохн Е.; Мотwани, Рајеев; Уллман, Јеффреy D. (2001), Интродуцтион то Аутомата Тхеорy, Лангуагес, анд Цомпутатион (2нд изд.), Аддисон-Wеслеy .
• Камеда, Тсунехико; Wеинер, Петер (1970), „Он тхе стате минимизатион оф нондетерминистиц фините аутомата”, ИЕЕЕ Трансацтионс он Цомпутерс, 100 (7), дои:10.1109/Т-C.1970.222994 .
• Кнуутила, Тимо (2001), „Ре-десцрибинг ан алгоритхм бy Хопцрофт”, Тхеоретицал Цомпутер Сциенце, 250 (1-2): 333—363, МР 1795249, дои:10.1016/С0304-3975(99)00150-4 .
• Леисс, Ернст (1981), „Суццинцт репресентатион оф регулар лангуагес бy Боолеан аутомата” (ПДФ), Тхеоретицал Цомпутер Сциенце, 13 (3): 323—330, МР 603263, дои:10.1016/С0304-3975(81)80005-9 .
• Леисс, Ернст (1985), „Суццинцт репресентатион оф регулар лангуагес бy Боолеан аутомата ИИ” (ПДФ), Тхеоретицал Цомпутер Сциенце, 38: 133—136, дои:10.1016/0304-3975(85)90215-4 
• Мооре, Едwард Ф. (1956), „Геданкен-еxпериментс он сеqуентиал мацхинес”, Аутомата студиес, Анналс оф матхематицс студиес, но. 34, Принцетон, Н. Ј.: Принцетон Университy Пресс, стр. 129—153, МР 0078059 .
• Сакаровитцх, Јацqуес (2009). Елементс оф аутомата тхеорy. Транслатед фром тхе Френцх бy Реубен Тхомас. Цамбридге Университy Пресс. ИСБН 978-0-521-84425-3. Збл 1188.68177. 

Спољашње везе

• ДФА минимизатион усинг тхе Мyхилл-Нероде тхеорем