Minimalisatie van een automaat

Met het minimaliseren van een automaat bedoelen we het vinden van een equivalente automaat met het kleinst mogelijke aantal toestanden. Ook een automaat zonder overbodige toestand kan nog verder worden vereenvoudigd.

Voorbeeld

Neem deze automaat:

De automaat accepteert alleen de woorden 01 en 11. Het is duidelijk dat er een eenvoudigere automaat met drie toestanden bestaat die dezelfde taal accepteert. De toestanden q₁ en q₂ kunnen we samenvoegen tot één nieuwe toestand {q₁, q₂}, en de overgangen die naar q₁ of q₂ liepen, lopen dan naar de nieuwe toestand, en hetzelfde geldt voor overgangen die uit q₁ en q₂ vertrekken. We krijgen deze automaat:

Deze automaat accepteert duidelijk dezelfde taal als de vorige en heeft tegelijk minder toestanden.

Equivalentie van toestanden

Neem een automaat A = ⟨Q, Σ, δ, q₀, F⟩. We definiëren de taal van een toestand q ∈ Q, genoteerd L(q), als

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

Dat wil zeggen: we veranderen de begintoestand van de automaat A van q₀ in q en berekenen de taal die door deze automaat wordt geaccepteerd. Met andere woorden: in de taal L(q) zitten alle woorden w waarvoor we in de automaat A vanuit toestand q met het woord w in een eindtoestand van de automaat komen. Als we teruggaan naar de vorige automaat, geldt L(q₁) = {1}.

We zeggen dat twee verschillende toestanden q₁ en q₂ equivalent zijn als

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

Wat betekent dat? Als de toestanden q₁, q₂ equivalent zijn, dan genereren ze dezelfde taal als we ze tot begintoestand van de automaat maken. Met andere woorden: als de automaat in de configuraties ⟨q₁, w⟩ en ⟨q₂, w⟩ komt, dan moet hij in beide gevallen accepteren of in beide gevallen verwerpen.

Terug naar de vorige automaat: de toestanden q₁ en q₂ zijn equivalent, want als we in toestand q₁ zitten, kunnen we het invoerwoord alleen nog accepteren als het nog niet gelezen deel van het woord gelijk is aan 1. Hetzelfde geldt als we in toestand q₂ zitten.

Bij het minimaliseren van een automaat gaat het er dus om equivalente toestanden te vinden en die te verwijderen door ze samen te voegen tot één nieuwe toestand, net zoals we in het voorbeeld hierboven hebben gedaan.

Hoe vind je equivalente toestanden

Welke toestanden zijn zeker niet equivalent? Een eindtoestand en een niet-eindtoestand zijn zeker niet equivalent, want de taal van een eindtoestand verschilt van de taal van een niet-eindtoestand — een eindtoestand accepteert zeker het woord ε, een niet-eindtoestand niet. We laten de werkwijze meteen aan een voorbeeld zien. Neem deze automaat:

We beginnen met het maken van twee verzamelingen toestanden

$\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 maken we een overgangstabel en houden we de informatie over de groepen S₁ en S₂ bij:

$\begin{array}{ccccc} groep & toestand & 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 passen we de tabel aan: in plaats van direct in de tabel op te schrijven naar welke toestanden we bij een bepaald symbool gaan, noteren we alleen de groep waarnaar we overgaan. Vanuit toestand q₃ komen we bij 0 bijvoorbeeld in toestand q₅, die in groep S₂ zit. In plaats van q₅ schrijven we dus S₂ in de tabel:

$\begin{array}{ccccc} groep & toestand & 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 splitsen we beide groepen verder. In dezelfde groep zetten we steeds toestanden die voor alle symbolen naar dezelfde groepen gaan. De toestanden q₃ en q₆ zitten bijvoorbeeld niet in dezelfde groep, omdat ze noch bij 0 noch bij 1 naar dezelfde groep gaan. De toestanden q₁ en q₂ zitten daarentegen wel in dezelfde groep, omdat beide toestanden geen overgang voor 0 hebben en beide toestanden bij 1 naar groep S₁ gaan. We maken zo nieuwe groepen:

$\begin{array}{ccccc} groep & toestand & 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}$

In elke groep hebben we dezelfde overgangen. We geven de nieuwe groepen een naam en bepalen weer naar welke van die nieuwe groepen de toestanden gaan:

$\begin{array}{ccccc} groep & toestand & 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}$

Op dit moment gaan we de groepen verder splitsen. We zien echter dat we geen verdere splitsing meer kunnen doen, we zouden dezelfde groepen krijgen — want de toestanden q₁ en q₂ hebben weliswaar dezelfde overgangen binnen de groepen, maar zitten al in dezelfde groep en er is geen andere toestand in groep S₄. Het algoritme voor het vinden van equivalente toestanden is ten einde. Uit elke groep hoeven we maar één toestand te kiezen, de rest verwijderen we, en alle overgangen die naar verwijderde toestanden liepen, lopen voortaan naar die ene toestand die we hebben gekozen.

We kunnen dus kiezen dat onze nieuwe automaat de toestanden q₃, q₆, q₀, q₁, q₄ heeft en de toestanden q₂ en q₅ verwijderen. Alle overgangen die naar q₂ liepen, lopen nu naar q₁ en alle overgangen die naar q₅ liepen, lopen naar q₄:

Werkwijze bij het minimaliseren van een automaat

We verwijderen de onbereikbare toestanden,
we verwijderen de overbodige toestanden,
we verwijderen de equivalente toestanden.

Bronnen

Hoofdstukken: Onbereikbare toestanden, Overbodige toestanden, Minimalisatie van een automaat

« Vorige: Overbodige toestanden

Volgende: Afsluitingseigenschappen van reguliere talen »