Minimering av automat

Med minimering av en automat mener vi å finne en ekvivalent automat som inneholder det minste mulige antallet tilstander. Selv en automat som ikke inneholder noen overflødig tilstand, kan forenkles videre.

Eksempel

La oss ta denne automaten:

Automaten aksepterer bare ordene 01 og 11. Det er åpenbart at det finnes en enklere automat med tre tilstander som aksepterer det samme språket. Tilstandene q₁ og q₂ kan slås sammen til én ny tilstand {q₁, q₂}, og overgangene som gikk til tilstandene q₁ eller q₂, vil gå til den nye tilstanden, og det samme gjelder for overgangene som gikk ut fra q₁ og q₂. Vi får denne automaten:

Denne automaten aksepterer åpenbart det samme språket som den forrige, og den har færre tilstander.

Ekvivalens av tilstander

La oss ha en automat A = ⟨Q, Σ, δ, q₀, F⟩. Vi definerer språket til tilstanden q ∈ Q, som vi betegner L(q), som

$L (q) = L (⟨ Q, Σ, δ, q, F ⟩)$

Det vil si at vi bytter starttilstanden i automaten A fra q₀ til q og regner ut språket som denne automaten aksepterer. Med andre ord inneholder språket L(q) alle ord w slik at vi i automaten A fra tilstanden q med ordet w kommer til en sluttilstand i automaten. Hvis vi går tilbake til den forrige automaten, er L(q₁) = {1}.

Vi sier at to ulike tilstander q₁ og q₂ er ekvivalente hvis

$L (q_{1}) = L (q_{2})$

Hva betyr dette? Hvis tilstandene q₁, q₂ er ekvivalente, vil de, hvis vi gjør dem til starttilstander i automaten, generere det samme språket. Med andre ord: hvis automaten kommer til konfigurasjonene ⟨q₁, w⟩ og ⟨q₂, w⟩, må den i begge tilfellene enten akseptere eller i begge tilfellene avvise.

Hvis vi går tilbake til den forrige automaten: tilstandene q₁ og q₂ er ekvivalente, for hvis vi er i tilstanden q₁, kan vi bare akseptere inputordet hvis den delen av ordet som ikke er lest, er lik 1. Det samme gjelder hvis vi er i tilstanden q₂.

Ved minimering av en automat gjelder det altså å finne ekvivalente tilstander og fjerne disse tilstandene ved å slå dem sammen til én ny tilstand, på samme måte som vi gjorde i eksempelet over.

Hvordan finne ekvivalente tilstander

Hvilke tilstander er helt sikkert ikke ekvivalente? Hvis vi tar en sluttilstand og en tilstand som ikke er en sluttilstand, er de helt sikkert ikke ekvivalente, for språket til sluttilstanden er forskjellig fra språket til tilstanden som ikke er en sluttilstand — sluttilstanden aksepterer helt sikkert ordet ε, men den andre gjør det ikke. Vi viser framgangsmåten med en gang på et eksempel. La oss ha denne automaten:

Vi begynner med å lage to mengder av tilstander

$\begin{array}{rcl} S_{1} & = & F = {q_{3}, q_{6}}, \\ S_{2} & = & Q ∖ F = {q_{0}, q_{1}, q_{2}, q_{4}, q_{5}} . \end{array}$

Nå lager vi en overgangstabell og beholder informasjonen om gruppene S₁ og S₂:

$\begin{array}{ccccc} gruppe & tilstand & 0 & 1 \\ S_{1} & q_{3} & q_{5} & q_{4} \\ q_{6} & — & — \\ S_{2} & q_{0} & q_{1} & q_{2} \\ q_{1} & — & q_{3} \\ q_{2} & — & q_{3} \\ q_{4} & q_{6} & — \\ q_{5} & q_{6} & — \end{array}$

Nå endrer vi tabellen slik at vi i stedet for å ha skrevet direkte hvilke tilstander vi går til for et gitt symbol, bare noterer gruppen vi går til. Fra tilstanden q₃ kommer vi for 0 for eksempel til tilstanden q₅, som er i gruppen S₂. I stedet for q₅ skriver vi derfor S₂ i tabellen:

$\begin{array}{ccccc} gruppe & tilstand & 0 & 1 \\ S_{1} & q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ S_{2} & q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

Nå deler vi begge gruppene videre. I de samme gruppene setter vi alltid tilstander som går til de samme gruppene for alle symboler. Tilstandene q₃ og q₆ vil for eksempel ikke være i samme gruppe, fordi de verken for 0 eller for 1 går til samme gruppe. Tilstandene q₁ og q₂ vil derimot være i samme gruppe, fordi begge tilstandene mangler en overgang for 0, og begge tilstandene går for 1 til gruppen S₁. Vi lager dermed nye grupper:

$\begin{array}{ccccc} gruppe & tilstand & 0 & 1 \\ q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

I hver gruppe har vi de samme overgangene. De nye gruppene gir vi navn og finner igjen ut hvilke av disse nye gruppene tilstandene peker til:

$\begin{array}{ccccc} gruppe & tilstand & 0 & 1 \\ S_{1} & q_{3} & S_{5} & S_{5} \\ S_{2} & q_{6} & — & — \\ S_{3} & q_{0} & S_{4} & S_{4} \\ S_{4} & q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ S_{5} & q_{4} & S_{2} & — \\ q_{5} & S_{2} & — \end{array}$

Nå deler vi gruppene enda en gang. Men vi ser at vi ikke kan dele mer, vi ville fått de samme gruppene — for tilstandene q₁ og q₂ har riktignok de samme overgangene innenfor gruppene, men de er allerede i samme gruppe, og det finnes ingen andre tilstander i gruppen S₄. Algoritmen for å finne ekvivalente tilstander er dermed ferdig. Fra hver gruppe er det nok å velge én tilstand, de andre sletter vi, og alle overganger som gikk til de slettede tilstandene, vil gå til den ene tilstanden vi valgte.

Vi kan altså velge at den nye automaten vår skal ha tilstandene q₃, q₆, q₀, q₁, q₄, og tilstandene q₂ og q₅ fjerner vi. Alle overganger som gikk til q₂, vil nå gå til q₁, og alle overganger som gikk til q₅, vil gå til q₄:

Framgangsmåte for minimering av automat

Vi fjerner uoppnåelige tilstander,
vi fjerner overflødige tilstander,
vi fjerner ekvivalente tilstander.

Kilder

Kapitler: Uoppnåelige tilstander, Overflødige tilstander, Minimering av automat

« Forrige: Overflødige tilstander

Neste: Lukkethetsegenskaper for regulære språk »