DKA minimizacija

Pod DKA minimizacijom se podrazumeva nalaženje determinističkog konačnog automata (DKA) sa najmanjim brojem stanja koji prepoznaje isti regularan jezik kao i zadati DKA. Pokazuje se da je ovaj automat jedinstven do na izomorfizam! Naime, za dva DKA ${\mathcal {A}}=(\Sigma ,Q,i,F,\delta )$ i ${\mathcal {B}}=(\Sigma ,Q',i',F',\delta {}')$ kažemo da su izomorfni ukoliko postoji bijekcija $f:Q\to Q'$ tako da je zadovoljeno :

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

Neformalno govoreći, ovo zapravo znači da ako imamo iscrtan multigraf kojim je predstavljen automat ${\mathcal {A}}$, možemo preimenovati stanja tog grafa (ostavljajući grane netaknutim i ne uvodeći nova početna niti završna stanja ) tako da se dobije multigraf automata ${\mathcal {B}}$. Dakle pri minimizaciji ne možemo dobiti suštinski različite automate i time se rešava pitanje jedinstvenosti. U daljem izlaganju koristićemo mestimično i proiširenu funkciju prelaza $\delta ^{*}(p,\omega )$
gde $p\in Q,\,\omega \in \Sigma ^{*}$, koja se definiše ovako:

• $\delta ^{*}(p,a)=\delta (p,a)$ kada $a\in \Sigma$
• $\delta ^{*}(p,\epsilon )=p$
• $\delta ^{*}(p,\omega a)=\delta (\delta ^{*}(p,\omega ),a)$ gde je $\omega$ neka reč: $|w|\geq 1$ i $a\in \Sigma$

U narednim sekcijama biće izložen skelet teorije koja se tiče minimalnog automata, a zatim će biti izloženo nekoliko algoritama za konstrukciju MDKA uz detaljna objašnjenja.

Minimalni automat preko levih količnika

Neka je dat DKA ${\mathcal {A}}=(\Sigma ,Q,i,F,\delta )$ koji prepoznaje jezik $L$, tj. $L={\mathcal {L}}({\mathcal {A}}).$
Pretpostavićemo da ovaj automat nema nedostupnih stanja, jer u suprotnom eliminacijom kompletnog podgrafa koji je indukovan nedostupnim stanjima automata dobijamo opet DKA, koji je ekvivalentan polaznom, a ima manje stanja. Ova pretpostavka dakle ne umanjuje opštost.

1. Za $u\in \Sigma ^{*}$ definišemo $u^{-1}X=\{w\in \Sigma ^{*}:uw\in X\}$ gde $X\subset \Sigma ^{*}$(Levi količnik skupa $X$ po reči $u$)
2. Definišemo i za svako $p\in Q\,\,$: ${\mathcal {L}}_{p}({\mathcal {A}})=\{\omega \in \Sigma ^{*}:\delta ^{*}(p,\omega )\in F\}$

Ako označimo $Q(L)=\{u^{-1}L:u\in \Sigma ^{*}\}$ može se pokazati da je $Q(L)=\{{\mathcal {L}}_{p}({\mathcal {A}}):p\in Q\}$, što zapravo povlači da je $Q(L)$ konačan i da je
$|Q(L)|\leq |Q|$ (*)
Sada možemo da konstruišemo DKA ${\mathcal {B}}=(\Sigma ,Q(L),L,F(L),{\overline {\delta }})$ na sledeći način:

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

Lako se može pokazati indukcijom po dužini reči $\omega$ da je ${\overline {\delta }}^{*}$ dobro definisana funkcija i da je ${\overline {\delta }}^{*}(Y,\omega )=\omega ^{-1}Y$, a odatle sledi ${\mathcal {L}}({\mathcal {A}})={\mathcal {L}}({\mathcal {B}})$, a to nije sve, na osnovu (*) zaključujemo da je ovaj automat zapravo DKA sa minimalnim brojem stanja koji je ekvivalentan sa ${\mathcal {A}}$, u smislu da ne postoji nijedan drugi automat sa tim svojstvom koji ima manje stanja.

Količnički automat i Nerodova ekvivalencija

Neka je ${\mathcal {A}}=(\Sigma ,Q,i,F,\delta )$ DKA u kome su sva stanja dostupna. Uvešćemo oznaku $L_{p}={\mathcal {L_{p}({\mathcal {A}})}}$ radi kraćeg zapisa. Neorodova relacija ekvivalencije nad $Q$
se definiše na sledeći način:

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

Za dva stanja koja su u u ovoj relaciji kažemo da su nerazlikujuća, u suprotnom ona su razlikujuća. Jedno važno svojstvo Nerodove relacije koja se eksploatiše u nekim algoritmima minimizacije DKA jeste desna invarijantnost tj.

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

Obeležićemo sa $[p]$ relaciju ekvivalencije elementa $p\in Q$, količnički skup sa $Q/\sim$.

• Količnički automat nad ${\mathcal {A}}$ je DKA ${\mathcal {A}}/\sim =(\Sigma ,Q/\sim ,[i],\{[f]|f\in F\},{\stackrel {\sim }{\delta }})$

za koji važi:${\stackrel {\sim }{\delta }}([p],a)=[\delta (p,a)]$.
Može se dokazati svaka klasa Nerodove ekvivalencije sadrži ili samo završna, ili samo nezavršna stanja, kao i da je ovaj (količnički) automat ekvivalentan polaznom. Količnički automat nad automatom ${\mathcal {A}}$ ima isto toliko stanja kao i minimalni automat opisan u prethodnoj sekciji što znači da je on takođe jedan minimalni automat za ${\mathcal {A}}$. Sa druga strane, može se pokazati da ukoliko je Nerodova relacija u stvari jednakost nad nekim DKA ${\mathcal {B}}$, onda je taj automat izomorfan sa minimalnim automatom opisanim u prethodnoj sekciji. Konačni zaključak je da su svaka dva minimalna automata za zadati DKA međusobno izomorfna, što znači da je pri minimizaciji dovoljno odrediti samo jedan, a obično je to upravo količnički automat.

Hopkroftov algoritam minimizacije

Ovaj algoritam kao i mnogi drugi algoritmi minimizacije se svodi na određivanje količničkog automata za neki DKA ${\mathcal {A}}$, odnosno određivanje klasa ekvivalencije Nerodove relacije. Ideja Hopkroftovog algoritma, je da najpre krenemo od nekog particionisanja ${\mathcal {P}}$ skupa stanja , tako da je svaka particija $P\in {\mathcal {P}}$ u stvari unija klasa ekvivalencija Nerodove relacije. (*)
Pošto svako particionisanje skupa određuje jednu relaciju ekvivalencije i obrnuto ( dva elementa su u toj relaciji akko su u istoj particiji) ovaj uslov bi mogao da se iskaže drugačije, tj. možemo da kažemo da u stvari želimo da krenemo od neke druge relacije ekvivalencije, za koju znamo da je nadskup Nerodove relacije, jer to znači da je količnički skup te relacije u stvari jedno particionisanje skupa stanja, i svaka klasa te relacije je ništa drugo nego unija nekih Nerodovih klasa ekvivalencije. Dakle, najpre definišemo neko particionisanje (relaciju) koje zadovoljava ovaj uslov, (a ono predstavlja grubu aproksimaciju Nerodove relacije), a zatim korak po korak dolazimo do sve finijih particija tj. do boljih aproksimacija, sve dok ne dobijemo količnički skup za Nerodovu relaciju ekvivalencije, u slučaju ovog algoritma videćemo da je to kada ne budemo više mogli da „proizvedemo” nove particije. Dakle uslov (*) se propagira u svakom koraku algoritma. Pre samog pseudokoda, par razjašnjenja i definicija koja se tiču ovog algoritma:

• Za dati DKA uvek možemo da pronađemo početno particionisanje, na primer $\{Q\backslash F,F\}$, budući da svaka Nerodova klasa sadrži samo završna ili samo nezavršna stanja, lako se vidi zbog čega ovo zadovoljava uslov (*). Slučaj kada je $F=\emptyset$ je trivijalan, jer tada količnički automat ima samo jedno stanje ! Tu je dakle posao završen na početku pa ćemo nadalje pretpostaviti da ovo neće da se desi.
• Ako imamo particiju ${\mathcal {P}}$ i $Y,Z\in {\mathcal {P}}$ i $c\in \Sigma$ onda ćemo reći da $Z$ „seče” particiju $Y$ po slovu $c$ ukoliko postoji neko stanje $p\in Y$ tako da $\delta (p,c)\in Z$ i takođe postoji $p\in Y$ tako da $\delta (p,c)\not \in Z$, dakle ako označimo $X=\{p\in Q:\delta (p,c)\in Z\}$ ovo prethodni uslovi mogu da se objedine u $Y\backslash X\neq \emptyset \wedge X\cap Y\neq \emptyset$.
• Ukoliko postoji particija $Z$ koja seče neku particiju $Y$ po nekom slovu $c$ onda zbog toga što je Nerodova ekvivalencija invarijantna nadesno, zaključujemo da se skup $Y$ može zameniti dvema manjim particijama $Y\backslash X$ i $X\cap Y$ gde je je skup $X$ definisan kao u gornjoj stavci, pri čemu se ne narušava uslov (*).
• Ukoliko ne postoji particija koja seče neku drugu particiju (ili samu sebe) po nekom slovu, onda to znači da smo došli do cilja, odnosno ovo particionisanje je količnički skup za Nerodovu relaciju.
• Da ne bismo vršili proveru po svakoj particiji tj. da li ona seče neku particiju iz tekućeg particionisanja, formiramo radnu list $W$ koja sadrži samo one particije koje je nužno proveriti i ažuriramo je kroz algoritam.

Pseudokod algoritma:

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;

Dokaz korektnosti algoritma se bazira na sledećim tvrđenjima (ciljna particija je ona koja se ne može dalje deliti, tj. ona je jedna klasa ekvivalencije Nerodove relacije )

• Tvrđenje 1 : za ${\mathcal {P}}=\{F,Q\backslash F\}$ i $W=\{F\}$ (odnosno $W=\{Q\backslash F\}$ ) važi $(\forall P\in {\mathcal {P}})$ ($P$ nije ciljna particija $\Leftrightarrow$ particija $F$ (odnosno $Q\backslash F$) seče $P$ po nekom slovu.

U svakom koraku algoritma, imaćemo particiju $P$ i radnu listu $W$ i ključan je uslov da ukoliko neka particija nije ciljna, onda nju obavezno seče neka particija iz $W$ po nekom slovu. Ovaj uslov takođe mora da se propagira kroz algoritam, a prethodno tvrđenje zapravo kazuje da je on ispunjen u prvom koraku algoritma. Ovaj uslov ćemo obeležiti sa (**).

• Tvrđenje 2: Neka particionisanje ${\mathcal {P}}$ i skup $W\subset {\mathcal {P}}$ zadovoljavaju uslov (**). I neka je $A\in W$. Tada ukoliko:

1. $A$ ne seče nijednu particiju iz ${\mathcal {P}}$, onda nova radna lista $W'=W\backslash \{A\}$ i particionisanje ${\mathcal {P}}$ zadovoljavaju uslov (**).
2. $A$ seče neku particiju $Y\not \in W$ po slovu $c$ i razlaže je na dve nove particije $Y',\,Y''$ onda novo particionisanje ${\mathcal {P'}}$ koje se dobija uklanjanjem $Y$ i dodavanjem dve nove particije $Y',\,Y''$ i nova radna lista $W'$ koja se dobija dodavanjem tačno jedne od novih particija (bilo koja) zadovoljavaju uslov (**)
3. $A$ seče neku particiju $Y\in W$ po slovu $c$ i razlaže je na dve nove particije $Y',\,Y''$ onda novo particionisanje ${\mathcal {P'}}$ koje se dobija uklanjanjem $Y$ i dodavanjem dve nove particije $Y',\,Y''$ i nova radna lista $W'=(W\cup \{Y',Y''\})\backslash \{Y\}$ zadovoljavaju uslov (**).

Ovo je najbrži algoritam, za minimizaciju automata koji je do sada poznat! Njegova vremenska složenost, uzimajući da je veličina azbuke konstantna je ${\mathcal {O}}(|Q|\cdot log|Q|)$. Ilustrujmo ovaj algoritam na jednom primeru.

Primer: Neka je $\Sigma =\{0,1\},\,Q=\{a,b,c,d,e,f\},i=a,F=\{c,d,e\}$ i funkcija prelaza $\delta$ data sledećom tablicom:

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

, Dakle automat ${\mathcal {A}}=(\Sigma ,Q,i,F,\delta )$ izgleda ovako:

Deterministički konačni automat kojeg treba minimalizovati

1. U početnom koraku inicijalizujemo početno particionisanje ${\mathcal {P}}=\{P_{1},P_{2}\}$ gde je $P_{1}=\{a,b,f\},P_{2}=\{c,d,e\}$ i radnu listu $W=\{P_{2}\}$.
2. Uzimamo neku particiju iz $W$ (to je za sada $P_{2}$ ) i određujemo skup svih stanja sa kojima se preko 0 dolazi u tu particiji i skup svih stanja sa kojima se preko 1 dolazi u tu particiju respektivno: $X(P_{2},0)=P_{2}$, $X(P_{2},1)=\{a,b\}$
3. Odavde vidimo da $P_{2}$ preko 0 ne seče ni jednu particiju, a preko 1 razdvaja $P_{1}$ u dve nove particije$\{a,b\}$ i $\{f\}$, dodajemo neku od ove dve particije (zbog optimizacije algoritma, onu manju) u $W$ istovremeno uklanjajući $P_{2}$ jer ona više neće seći nijednu particiju. Novo particionisanje je sada ${\mathcal {P'}}=\{P_{1}',P_{2}',P_{3}'\}$ gde je $P_{1}'=\{a,b\},\,P_{2}'=\{f\},P_{3}'=\{c,d,e\}$ a nova radna lista je $W'=\{P_{2}'\}$.
4. Sada razmatramo $P_{2}'$ : $X(P_{2}',0)=\{f\},\,\,X(P_{2}',1)=\{c,d,e,f\}$, a odavde vidimo da $P_{2}'$ ne seče ni jednu particiju ni preko 0 a ni preko 1 a kako nemamo drugih elemenata u $W'$ ovde se algoritam završava i dobili smo traženi količnički skup.

Dakle količnički (minimalni) automat izgleda ovako:

Minimalizovani DKA

Literatura

• Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974), „4.13 Partitioning”, The Design and Analysis of Computer Algorithms, Addison-Wesley, стр. 157—162 .
• Berstel, Jean; Boasson, Luc; Carton, Olivier; Fagnot, Isabelle (2010), „Minimization of Automata”, Automata: from Mathematics to Applications, European Mathematical Society, arXiv:1010.5318  
• Brzozowski, J. A. (1963), „Canonical regular expressions and minimal state graphs for definite events”, Proc. Sympos. Math. Theory of Automata (New York, 1962), Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y., стр. 529—561, MR 0175719 .
• Câmpeanu, Cezar; Culik, Karel, II; Salomaa, Kai; Yu, Sheng (2001), „State Complexity of Basic Operations on Finite Languages”, 4th International Workshop on Automata Implementation (WIA '99), Lecture Notes in Computer Science, 2214, Springer-Verlag, стр. 60—70, doi:10.1007/3-540-45526-4_6 .
• David, Julien (2012), „Average complexity of Moore’s and Hopcroft’s algorithms”, Theoretical Computer Science, 417: 50—65, doi:10.1016/j.tcs.2011.10.011 .
• Hopcroft, John (1971), „An n log n algorithm for minimizing states in a finite automaton”, Theory of machines and computations (Proc. Internat. Sympos., Technion, Haifa, 1971), New York: Academic Press, стр. 189—196, MR 0403320 . See also preliminary version, Technical Report STAN-CS-71-190, Stanford University, Computer Science Department, January 1971.
• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001), Introduction to Automata Theory, Languages, and Computation (2nd изд.), Addison-Wesley .
• Kameda, Tsunehiko; Weiner, Peter (1970), „On the state minimization of nondeterministic finite automata”, IEEE Transactions on Computers, 100 (7), doi:10.1109/T-C.1970.222994 .
• Knuutila, Timo (2001), „Re-describing an algorithm by Hopcroft”, Theoretical Computer Science, 250 (1-2): 333—363, MR 1795249, doi:10.1016/S0304-3975(99)00150-4 .
• Leiss, Ernst (1981), „Succinct representation of regular languages by Boolean automata” (PDF), Theoretical Computer Science, 13 (3): 323—330, MR 603263, doi:10.1016/S0304-3975(81)80005-9 .
• Leiss, Ernst (1985), „Succinct representation of regular languages by Boolean automata II” (PDF), Theoretical Computer Science, 38: 133—136, doi:10.1016/0304-3975(85)90215-4 
• Moore, Edward F. (1956), „Gedanken-experiments on sequential machines”, Automata studies, Annals of mathematics studies, no. 34, Princeton, N. J.: Princeton University Press, стр. 129—153, MR 0078059 .
• Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177. 

Spoljašnje veze

• DFA minimization using the Myhill-Nerode theorem