Minimering af automat

Ved minimering af en automat forstår vi at finde en ækvivalent automat, som indeholder det mindst mulige antal tilstande. Selv en automat, der ikke indeholder nogen overflødig tilstand, kan forenkles yderligere.

Eksempel

Lad os tage denne automat:

Automaten accepterer kun ordene 01 og 11. Det er samtidig tydeligt, at der findes en enklere automat med tre tilstande, som accepterer det samme sprog. Tilstandene q₁ og q₂ kan slås sammen til én ny tilstand {q₁, q₂}, og de overgange, der førte til tilstandene q₁ eller q₂, vil føre til den nye tilstand, og det samme gælder for overgange, der udgår fra q₁ og q₂. Vi får denne automat:

Denne automat accepterer åbenlyst det samme sprog som den foregående og har samtidig færre tilstande.

Ækvivalens af tilstande

Vi har en automat A = ⟨Q, Σ, δ, q₀, F⟩. Vi definerer sproget for tilstanden q ∈ Q, som vi betegner L(q), således

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

Det vil sige, at vi ændrer automatens A starttilstand fra q₀ til q og bestemmer det sprog, som denne automat accepterer. Med andre ord er alle ord w i sproget L(q) sådan, at vi i automaten A kommer fra tilstanden q til en accepttilstand i automaten for ordet w. Hvis vi vender tilbage til den foregående automat, så er L(q₁) = {1}.

Vi siger, at to forskellige tilstande q₁ og q₂ er ækvivalente, hvis

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

Hvad betyder det? Hvis tilstandene q₁, q₂ er ækvivalente, så vil de, hvis vi gør dem til automatens starttilstande, generere det samme sprog. Med andre ord: hvis automaten kommer i konfigurationen ⟨q₁, w⟩ og ⟨q₂, w⟩, så skal den enten acceptere i begge tilfælde eller afvise i begge tilfælde.

Hvis vi vender tilbage til den foregående automat: tilstandene q₁ og q₂ er ækvivalente, for hvis vi er i tilstanden q₁, kan vi kun acceptere inputordet, hvis den endnu ikke læste del af ordet er lig med 1. Det samme gælder, hvis vi er i tilstanden q₂.

Ved minimering af en automat handler det altså om at finde ækvivalente tilstande og fjerne dem ved at slå dem sammen til én ny tilstand, ligesom vi gjorde i eksemplet ovenfor.

Sådan finder du ækvivalente tilstande

Hvilke tilstande er helt sikkert ikke ækvivalente? Hvis vi tager en accepttilstand og en ikke-accepterende tilstand, er de helt sikkert ikke ækvivalente, fordi sproget for accepttilstanden er forskelligt fra sproget for den ikke-accepterende tilstand — en accepttilstand accepterer helt sikkert ordet ε, en ikke-accepterende tilstand gør ikke. Vi viser fremgangsmåden direkte på et eksempel. Vi ser på denne automat:

Vi begynder med at danne to mængder af tilstande

$\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}$

Nu danner vi en overgangstabel og bevarer oplysningen om grupperne 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}$

Nu ændrer vi tabellen, så vi i stedet for direkte at skrive, hvilke tilstande man kommer til for det pågældende symbol, kun noterer den gruppe, vi går over 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}$

Nu deler vi begge grupper yderligere. I samme grupper placerer vi altid tilstande, der for alle symboler går over til de samme grupper. Tilstandene q₃ og q₆ vil for eksempel ikke være i samme gruppe, fordi de hverken for 0 eller for 1 går til den samme gruppe. Tilstandene q₁ og q₂ derimod vil være i samme gruppe, fordi begge tilstande mangler en overgang for 0, og begge tilstande går for 1 til gruppen S₁. Vi danner 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 overgange. De nydannede grupper betegner vi og finder igen ud af, til hvilke af disse nye grupper tilstandene går:

$\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}$

På dette tidspunkt foretager vi endnu en deling af grupperne. Men vi ser, at vi ikke kan foretage flere delinger, vi ville få de samme grupper — for tilstandene q₁ og q₂ har ganske vist de samme overgange inden for grupperne, men de er allerede i samme gruppe, og ingen anden tilstand i gruppen S₄ findes. Algoritmen til at finde ækvivalente tilstande er færdig. Fra hver gruppe er det nok at vælge én tilstand, de øvrige sletter vi, og alle overgange, der førte til slettede tilstande, vil føre til den ene tilstand, vi valgte.

Vi kan altså vælge, at vores nye automat skal have tilstandene q₃, q₆, q₀, q₁, q₄, og tilstandene q₂ og q₅ fjerner vi. Alle overgange, der førte til q₂, vil nu føre til q₁, og alle overgange, der førte til q₅, vil føre til q₄:

Fremgangsmåde ved minimering af en automat

Vi fjerner uopnåelige tilstande,
vi fjerner overflødige tilstande,
vi fjerner ækvivalente tilstande.

Kilder

Kapitler: Uopnåelige tilstande, Overflødige tilstande, Minimering af automat

« Forrige: Overflødige tilstande

Næste: Lukkethedsegenskaber for regulære sprog »