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.[1] Pokazuje se da je ovaj automat jedinstven do na izomorfizam! Naime, za dva DKA i kažemo da su izomorfni ukoliko postoji bijekcija tako da je zadovoljeno :

Neformalno govoreći, ovo zapravo znači da ako imamo iscrtan multigraf kojim je predstavljen automat , 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 . 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
gde , koja se definiše ovako:

  • kada
  • gde je neka reč: i

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   koji prepoznaje jezik  , tj.  
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   definišemo   gde  (Levi količnik skupa   po reči  )
  2. Definišemo i za svako  :  

Ako označimo   može se pokazati da je  , što zapravo povlači da je   konačan i da je
  (*)
Sada možemo da konstruišemo DKA   na sledeći način:

  •  
  •  

Lako se može pokazati indukcijom po dužini reči   da je   dobro definisana funkcija i da je  , a odatle sledi  , a to nije sve, na osnovu (*) zaključujemo da je ovaj automat zapravo DKA sa minimalnim brojem stanja koji je ekvivalentan sa  , u smislu da ne postoji nijedan drugi automat sa tim svojstvom koji ima manje stanja.

Količnički automat i Nerodova ekvivalencija

уреди

Neka je   DKA u kome su sva stanja dostupna. Uvešćemo oznaku   radi kraćeg zapisa. Neorodova relacija ekvivalencije nad  
se definiše na sledeći način:

  •  

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.

  •  .

Obeležićemo sa   relaciju ekvivalencije elementa  , količnički skup sa  .

  • Količnički automat nad   je DKA  

za koji važi: .
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   ima isto toliko stanja kao i minimalni automat opisan u prethodnoj sekciji što znači da je on takođe jedan minimalni automat za  . Sa druga strane, može se pokazati da ukoliko je Nerodova relacija u stvari jednakost nad nekim DKA  , 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  , odnosno određivanje klasa ekvivalencije Nerodove relacije. Ideja Hopkroftovog algoritma, je da najpre krenemo od nekog particionisanja   skupa stanja , tako da je svaka particija   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  , 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   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   i   i   onda ćemo reći da   „seče” particiju   po slovu   ukoliko postoji neko stanje   tako da   i takođe postoji   tako da  , dakle ako označimo   ovo prethodni uslovi mogu da se objedine u  .
  • Ukoliko postoji particija   koja seče neku particiju   po nekom slovu   onda zbog toga što je Nerodova ekvivalencija invarijantna nadesno, zaključujemo da se skup   može zameniti dvema manjim particijama   i   gde je je skup   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   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   i   (odnosno   ) važi   (  nije ciljna particija   particija   (odnosno  ) seče   po nekom slovu.

U svakom koraku algoritma, imaćemo particiju   i radnu listu   i ključan je uslov da ukoliko neka particija nije ciljna, onda nju obavezno seče neka particija iz   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   i skup   zadovoljavaju uslov (**). I neka je  . Tada ukoliko:
  1.   ne seče nijednu particiju iz  , onda nova radna lista   i particionisanje   zadovoljavaju uslov (**).
  2.   seče neku particiju   po slovu   i razlaže je na dve nove particije   onda novo particionisanje   koje se dobija uklanjanjem   i dodavanjem dve nove particije   i nova radna lista   koja se dobija dodavanjem tačno jedne od novih particija (bilo koja) zadovoljavaju uslov (**)
  3.   seče neku particiju   po slovu   i razlaže je na dve nove particije   onda novo particionisanje   koje se dobija uklanjanjem   i dodavanjem dve nove particije   i nova radna lista   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  . Ilustrujmo ovaj algoritam na jednom primeru.

Primer: Neka je   i funkcija prelaza   data sledećom tablicom:

             
0            
1            

, Dakle automat   izgleda ovako:

 
Deterministički konačni automat kojeg treba minimalizovati
  1. U početnom koraku inicijalizujemo početno particionisanje   gde je   i radnu listu  .
  2. Uzimamo neku particiju iz   (to je za sada   ) 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:  ,  
  3. Odavde vidimo da   preko 0 ne seče ni jednu particiju, a preko 1 razdvaja   u dve nove particije  i  , dodajemo neku od ove dve particije (zbog optimizacije algoritma, onu manju) u   istovremeno uklanjajući   jer ona više neće seći nijednu particiju. Novo particionisanje je sada   gde je   a nova radna lista je  .
  4. Sada razmatramo   :  , a odavde vidimo da   ne seče ni jednu particiju ni preko 0 a ni preko 1 a kako nemamo drugih elemenata u   ovde se algoritam završava i dobili smo traženi količnički skup.

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

 
Minimalizovani DKA

Reference

уреди
  1. ^ Hopcroft, Motwani & Ullman 2001, Section 4.4.3, "Minimization of DFA's".

Literatura

уреди

Spoljašnje veze

уреди