Minimizacija konačnog automata

Minimizacija konačnog automata je postupak izgradnje konačnog automata koji je istovjetan (tj. prihvaća isti jezik), i koji sadrži što je moguće manji broj stanja. Općenito je za bilo koji 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F)} je istovjetno stanju $p'$ DKA Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle M=(Q',\Sigma ,\delta ',q_{0}',F')} ako i samo ako DKA M u stanju p prihvaća isti skup nizova kao i DKA Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle M'} u stanju $p'$. Za bilo koji niz w skupa Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \Sigma *} vrijedi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \delta (p,w)\in F\wedge \delta '(p'w)\in F'} ili Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \delta (p,w)\notin F\wedge \delta '(p'w)\notin F'} .

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:

1. Uvjet podudarnosti: Stanja p i q moraju oba biti prihvatljiva (Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p\in F\wedge q\in F} ) ili oba neprihvatljiva (Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p\notin F\wedge q\notin F} ).
2. Uvjet napredovanja: Za bilo koji ulazni znak Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a\in \Sigma } vrijedi da su stanja Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \delta (p,a)} i Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \delta (q,a)} 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F)} 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p\in F}
), a drugi podskup sva
   stanja koja nisu prihvatljiva (sva stanja Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle q\notin F}
). Označimo simbolom Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \Pi }
 podjelu skupa stanja u ta dva podskupa.

2) Primjenimo sljedeći algoritam:
     za (sve particije ekvivalencije Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle G_{j}\in \Pi }
)
     {
       Podijeli particiju Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle G_{j}}
 u potparticije tako da su dva stanja p i q iz particije Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle G_{j}}
 u istoj potparticiji ako i samo ako za bilo
       koji ulazni znak a vrijedi:

       Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \delta (p,a)\in G_{i}\wedge \delta (q,a)\in G_{i}}
, za neku particiju Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle G_{i}\in \Pi }


       // Za različite ulazne znakove a particije Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle G_{i}}
 mogu biti različite

       Označi novu podjelu particija Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \Pi _{nova}}
;
     }

 3) Ako je podjela na potparticije ostala ista, tj. ako je $\Pi _{nova}=\Pi$, tada se algoritam zaustavlja, i stanja u istim particijama
    ekvivalencije su istovjetna. Ako je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \Pi _{nova}\neq \Pi }
, tada nastavi algoritam korakom (2) sa Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \Pi =\Pi _{nova}}

Implikacijska tablica

Ovaj je algoritam pesimističan u smislu da traži neistovjetna stanja. Označi li se par stanja (p, q) DKA $M=(Q,\Sigma ,\delta ,q_{0},F)$ algoritmom koji je prikazan dolje, dva stanja p i q su neistovjetna.

Označi sve parove (p, q) takve da je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p\in F}
 i Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle q\notin F}


za (Bilo koji par različitih stanja $(p,q)\in \left({F\times F}\right)$ ili Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (p,q)\notin \left({F\times F}\right)}
)
{
  ako (Za neki znak a par Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (\delta (p,a),\delta (q,a))}
 jest označen
  {
    Označi (p, q);

    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;
  }
  inače
  {
    za (Svi znakovi a)
    {
      ako ($\delta (p,a)\neq \delta (q,a)$)
      Stavi (p, q) u listu koja je pridružena paru Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (\delta (p,a),\delta (q,a))}
;
    }
  }
}

Nedohvatljiva stanja

Stanje p DKA $M=(Q,\Sigma ,\delta ,q_{0},F)$ jest nedohvatljivo stanje ako ne postoji niti jedan niz $w\in \Sigma *$ za koji vrijedi Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p = \delta(q_0,w)} . Odbacivanjem nedohvatljivih stanja dobije se istovjetni DKA s manjim brojem stanja.

Dohvatljiva stanja DKA Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M = (Q,\Sigma ,\delta ,q_0 ,F)} se određuju sljedećim algoritmom:

1) U listu dohvatljivih stanja DS upiše se početno stanje Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_0}
.

2) Lista DS proširi se skupom stanja Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{ {p|p = \delta (q_i ,a),\mathrm{za\ sve\ }a \in \Sigma } \right\}}
.

3) Za sva stanja Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_i \in DS}
 proširi se lista skupom stanja Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{ {p|p = \delta (q_i ,a),\mathrm{stanje\ p\ nije\ prethodno\ zapisano\ u\ listu\ }a \in \Sigma } \right\}}
.

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 NKA i Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon} -NKA, se uvijek mogu svesti na DKA i na na taj se način može primjeniti isti minimizacijski postupak.