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  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.
 Za  definišemo  gde (Levi količnik skupa  po reči )
 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:
  ne seče nijednu particiju iz , onda nova radna lista  i particionisanje  zadovoljavaju uslov (**).
  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 (**)
  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: 

, Dakle automat  izgleda ovako:

 U početnom koraku inicijalizujemo početno particionisanje  gde je  i radnu listu .
 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: , 
 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 .
 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:

Reference

Literatura 

 .
 
 .
 .
 .
 . See also preliminary version, Technical Report STAN-CS-71-190, Stanford University, Computer Science Department, January 1971.
 .
 .
 .
 .
  
 .

Spoljašnje veze 
 DFA minimization using the Myhill-Nerode theorem

Коначни аутомати
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 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 . Za definišemo gde ( Levi količnik skupa po reči ) 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 : 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 Neka particionisanje i skup zadovoljavaju uslov ( * * ) . I neka je \ . Tada ukoliko : ne seče nijednu particiju iz , onda nova radna lista i particionisanje zadovoljavaju uslov ( * * ). 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 ( * * ) 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 : Dakle automat izgleda ovako : U početnom koraku inicijalizujemo početno particionisanje gde je i radnu listu \ . Uzimamo neku particiju iz ( to je za sada ) i određujemo skup svih stanja sa kojima se prekodolazi u tu particiji i skup svih stanja sa kojima se prekodolazi u tu particiju respektivno : , Odavde vidimo da prekone seče ni jednu particiju , a prekorazdvaja 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 \ . Sada razmatramo \ : , a odavde vidimo da ne seče ni jednu particiju ni prekoa ni prekoa 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 : Reference Literatura \ . \ . \ . \ . \ . See also preliminary version , Technical Report STAN-CS-71-190 , Stanford University , Computer Science Department , January \ . \ . \ . \ . \ . Spoljašnje veze DFA minimization using the Myhill-Nerode theorem Коначни аутомати