Minimering av automater

Med minimering av en automat menar vi att hitta en ekvivalent automat som har så få tillstånd som möjligt. Även en automat som inte innehåller något överflödigt tillstånd kan förenklas ytterligare.

Exempel

Låt oss ta den här automaten:

Automaten accepterar bara orden 01 och 11. Det är uppenbart att det finns en enklare automat med tre tillstånd som accepterar samma språk. Tillstånden q₁ och q₂ kan slås ihop till ett nytt tillstånd {q₁, q₂}, och de övergångar som ledde till q₁ eller q₂ leder nu till det nya tillståndet, och detsamma gäller övergångarna som utgick från q₁ och q₂. Vi får den här automaten:

Den här automaten accepterar uppenbarligen samma språk som den förra och har dessutom färre tillstånd.

Ekvivalenta tillstånd

Låt A = ⟨Q, Σ, δ, q₀, F⟩ vara en automat. Vi definierar språket för tillståndet q ∈ Q, betecknat L(q), som

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

Det vill säga att vi byter automatens A starttillstånd från q₀ till q och bestämmer språket som den automaten accepterar. Med andra ord innehåller språket L(q) alla ord w sådana att vi i automaten A från tillståndet q med ordet w kommer till ett sluttillstånd. Om vi återvänder till den förra automaten är L(q₁) = {1}.

Vi säger att två olika tillstånd q₁ och q₂ är ekvivalenta om

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

Vad betyder det? Om tillstånden q₁, q₂ är ekvivalenta och vi gör dem till starttillstånd i automaten, så genererar de samma språk. Med andra ord: om automaten hamnar i konfigurationen ⟨q₁, w⟩ respektive ⟨q₂, w⟩, så måste den antingen acceptera i båda fallen eller förkasta i båda fallen.

Om vi återvänder till den förra automaten: tillstånden q₁ och q₂ är ekvivalenta, eftersom vi i q₁ bara kan acceptera indataordet om den olästa delen av ordet är 1. Detsamma gäller om vi är i q₂.

Vid minimering av en automat gäller det alltså att hitta ekvivalenta tillstånd och ta bort dem genom att slå ihop dem till ett nytt tillstånd, på samma sätt som vi gjorde i exemplet ovan.

Hur du hittar ekvivalenta tillstånd

Vilka tillstånd är säkert inte ekvivalenta? Om vi tar ett sluttillstånd och ett tillstånd som inte är ett sluttillstånd är de säkert inte ekvivalenta, eftersom språket för sluttillståndet skiljer sig från språket för det andra. Sluttillståndet accepterar säkert ordet ε, det andra gör det inte. Vi visar förfarandet direkt med ett exempel. Låt oss ta den här automaten:

Vi börjar med att skapa två mängder av tillstånd

$\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 skapar vi en övergångstabell och behåller informationen om grupperna S₁ och S₂:

$\begin{array}{ccccc} grupp & tillstånd & 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 ändrar vi tabellen så att vi i stället för att skriva direkt vilka tillstånd vi kommer till för en viss symbol bara antecknar vilken grupp vi går till. Från tillståndet q₃ kommer vi till exempel för 0 till q₅, som ligger i gruppen S₂. I stället för q₅ skriver vi alltså S₂ i tabellen:

$\begin{array}{ccccc} grupp & tillstånd & 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 delar vi upp båda grupperna ytterligare. I samma grupp lägger vi alltid de tillstånd som för alla symboler går till samma grupper. Tillstånden q₃ och q₆ hamnar till exempel inte i samma grupp, eftersom de varken för 0 eller för 1 går till samma grupp. Däremot hamnar q₁ och q₂ i samma grupp, eftersom båda saknar övergång för 0 och båda går för 1 till gruppen S₁. Vi skapar alltså nya grupper:

$\begin{array}{ccccc} grupp & tillstånd & 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 varje grupp har vi nu samma övergångar. Vi namnger de nya grupperna och tar återigen reda på till vilka av de nya grupperna tillstånden går:

$\begin{array}{ccccc} grupp & tillstånd & 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}$

Nu delar vi upp grupperna ännu en gång. Vi ser dock att vi inte kan göra någon ytterligare uppdelning, eftersom vi skulle få samma grupper. Tillstånden q₁ och q₂ har visserligen samma övergångar mellan grupperna, men de ligger redan i samma grupp, och inget annat tillstånd finns i gruppen S₄. Algoritmen för att hitta ekvivalenta tillstånd är därmed klar. Från varje grupp räcker det att vi väljer ett tillstånd. De övriga tar vi bort, och alla övergångar som ledde till de borttagna tillstånden leder i stället till det enda tillstånd som vi valde.

Vi kan alltså välja att vår nya automat får tillstånden q₃, q₆, q₀, q₁, q₄, och tillstånden q₂ och q₅ tar vi bort. Alla övergångar som ledde till q₂ leder nu till q₁, och alla övergångar som ledde till q₅ leder till q₄:

Så minimerar du en automat

Vi tar bort onåbara tillstånd,
vi tar bort överflödiga tillstånd,
vi tar bort ekvivalenta tillstånd.

Källor

Kapitel: Onåbara tillstånd, Överflödiga tillstånd, Minimering av automater

« Föregående: Överflödiga tillstånd

Nästa: Slutenhetsegenskaper för reguljära språk »