Vidi kôd stranice Minimizacija konačnog automata

Minimizacija konačnog automata''' je postupak izgradnje [[konačni automat|konačnog automata]] koji je istovjetan (tj. prihvaća isti [[formalni jezik|jezik]]), i koji sadrži što je moguće manji broj [[stanje (računarstvo)|stanja]]. Općenito je za bilo koji [[deterministički konačni automat|DKA]] moguće izgraditi beskonačno mnogo drugih DKA koji prihvaćaju isti jezik. Mininimizacija broja stanja dovodi do učinkovitijeg programskog ili sklopovskog ostvarenja automata.

== Istovjetnost stanja i automata ==

Stanje ''p'' DKA <math> M = (Q,\Sigma ,\delta ,q_0 ,F)</math> je istovjetno stanju <math>p'</math> DKA <math> M = (Q',\Sigma ,\delta ',q_0 ',F')</math> ako i samo ako DKA ''M'' u stanju ''p'' prihvaća isti skup nizova kao i DKA <math>M'</math> u stanju <math>p'</math>. Za bilo koji niz ''w'' skupa <math>\Sigma *</math> vrijedi <math>\delta (p,w) \in F \wedge \delta '(p'w) \in F'</math> ili <math>\delta (p,w) \notin F \wedge \delta '(p'w) \notin F'</math>.

[[Relacija ekvivalencije]] (tj. istovjetnosti) jest po definiciji tranzitivna, pa iz istovjetnosti stanja ''p'' i ''q'', i istovjetnosti stanja ''q'' i ''r'', slijedi istovjetnost stanja ''p'' i ''r''.

Istovjetnost DKA jest izrađena nad definicijom istovjetnosti stanja: DKA ''M'' i ''N'' su istovjetni ako i samo ako su istovjetna njihova početna stanja.

Ispitivanje istovjetnosti stanja se može svesti na ispitivanje dva uvjeta:
#''Uvjet podudarnosti'': Stanja ''p'' i ''q'' moraju oba biti prihvatljiva (<math>p \in F \wedge q \in F</math>) ili oba neprihvatljiva (<math>p \notin F \wedge q \notin F</math>).
#''Uvjet napredovanja'': Za bilo koji ulazni znak <math>a \in \Sigma</math> vrijedi da su stanja <math>\delta (p,a)</math> i <math>\delta (q,a)</math> istovjetna.

== Određivanje istovjetnih stanja ==

Postoji mnogo algoritama za određivanje istovjetnih stanja automata, i svi na neki način računski pojednostavljuju osnovnu definiciju istovjetnosti preko uvjeta podudarnosti i napredovanja.

=== Mooreov redukcijski postupak ===

Algoritam dijeli skup stanja DKA <math>M = (Q,\Sigma ,\delta ,q_0 ,F)</math> u podskupove na temelju uvjeta podudarnosti. Te podskupove zovemo '''particije ekvivalencije'''. 

Klase ekvivalencije su pobrojane po broju koraka koji je bio potreban da se dođe do nje, počevši od nulte particije. Stanja koja se mogu razlikovati (razabrati) u k-toj particiji se zovu '''k-razaberiva''' stanja. Stanja koja su u istom podskupu su '''k-ekvivalentna'''. Stanja koja su k-ekvivalentna u jednom koraku nisu nužno istovjetna, pošto u nekom od sljedećih koraka mogu biti razdvojena u različite particije ekvivalencije.

[[Pseudokod]] algoritama se može prikazati u tri koraka:

 1) Skup stanja se podijeli u dva podskupa. Jedan podskup sadrži sva prihvatljiva stanja (sva stanja <math>p \in F</math>), a drugi podskup sva
    stanja koja nisu prihvatljiva (sva stanja <math>q \notin F</math>). Označimo simbolom <math>\Pi</math> podjelu skupa stanja u ta dva podskupa.<br>
 2) Primjenimo sljedeći algoritam:
      <u>za</u> (sve particije ekvivalencije <math>G_j \in \Pi</math>)
      {
        Podijeli particiju <math>G_j</math> u potparticije tako da su dva stanja ''p'' i ''q'' iz particije <math>G_j</math> u istoj potparticiji ako i samo ako za bilo
        koji ulazni znak ''a'' vrijedi:<br>
        <math>\delta (p,a) \in G_i  \wedge \delta (q,a) \in G_i</math>, za neku particiju <math>G_i \in \Pi</math><br>
        // Za različite ulazne znakove ''a'' particije <math>G_i</math> mogu biti različite<br>
        Označi novu podjelu particija <math>\Pi _{nova}</math>;
      }<br>
  3) Ako je podjela na potparticije ostala ista, tj. ako je <math>\Pi _{nova} = \Pi</math>, tada se algoritam zaustavlja, i stanja u istim particijama
     ekvivalencije su istovjetna. Ako je <math>\Pi _{nova} \ne \Pi</math>, tada nastavi algoritam korakom (2) sa <math>\Pi = \Pi _{nova}</math>

=== Implikacijska tablica ===

Ovaj je algoritam ''pesimističan'' u smislu da traži neistovjetna stanja. Označi li se par stanja ''(p, q)'' DKA <math>M = (Q,\Sigma ,\delta ,q_0 ,F)</math> algoritmom koji je prikazan dolje, dva stanja ''p'' i ''q'' su neistovjetna.

 Označi sve parove ''(p, q)'' takve da je <math>p \in F</math> i <math>q \notin F</math><br>
 <u>za</u> (Bilo koji par različitih stanja <math>(p,q) \in \left( {F \times F} \right)</math> ili <math>(p,q) \notin \left( {F \times F} \right)</math>)
 {
   <u>ako</u> (Za neki znak ''a'' par <math>(\delta (p,a),\delta (q,a))</math> jest označen
   {
     Označi ''(p, q)'';<br>
     Rekurzivno označi sve neoznačene parove u listi koja je pridružena paru ''(p, q)'' i sve ostale parove u listama koje su pridružene 
     parovima označenim u ovom koraku;
   }
   <u>inače</u>
   {
     <u>za</u> (Svi znakovi ''a'')
     {
       <u>ako</u> (<math>\delta (p,a) \ne \delta (q,a)</math>)
       Stavi ''(p, q)'' u listu koja je pridružena paru <math>(\delta (p,a),\delta (q,a))</math>;
     }
   }
 }

== Nedohvatljiva stanja ==

Stanje ''p'' DKA <math>M = (Q,\Sigma ,\delta ,q_0 ,F)</math> jest '''nedohvatljivo stanje''' ako ne postoji niti jedan niz <math>w \in \Sigma *</math> za koji vrijedi <math>p = \delta(q_0,w)</math>. Odbacivanjem nedohvatljivih stanja dobije se istovjetni DKA s manjim brojem stanja. 

Dohvatljiva stanja DKA <math>M = (Q,\Sigma ,\delta ,q_0 ,F)</math> se određuju sljedećim algoritmom:
 
 1) U listu dohvatljivih stanja ''DS'' upiše se početno stanje <math>q_0</math>.<br>
 2) Lista DS proširi se skupom stanja <math>\left\{ {p|p = \delta (q_i ,a),\mathrm{za\ sve\ }a \in \Sigma } \right\}</math>.<br>
 3) Za sva stanja <math>q_i \in DS</math> proširi se lista skupom stanja <math>\left\{ {p|p = \delta (q_i ,a),\mathrm{stanje\ p\ nije\ prethodno\ zapisano\ u\ listu\ }a \in \Sigma } \right\}</math>.<br>

Ukoliko se lista dohvatljivih stanja proširi zapisom novog stanja, tada se rad algoritma nastavlja korakom (3) priloženog pseudokoda. Lista ''DS'' sadrži sva dohvatljiva stanja, dok su sva ostala stanja nedohvatljiva.

== DKA s minimalnim brojem stanja ==

Odbacivanjem istovjetnih i nedohvatljivih stanja dobije se istovjetni DKA s minimalnim brojem stanja. U postupku minimizacije je učinkovitije prvo primjeniti postupak odbacivanja nedohvatljivih stanja, a tek potom postupak odbacivanja istovjetnih stanja.

Ostali konačni automati, kao što su [[nedeterministički konačni automat|NKA]] i <math>\epsilon</math>-[[nedeterministički konačni automat|NKA]], se uvijek mogu svesti na DKA i na na taj se način može primjeniti isti minimizacijski postupak.
[[Kategorija:Teorija automata]]