Eindige automaat

Een eindige automaat (Engels finite state machine of finite automaton) is een rekenmodel van een primitieve computer. Hij bestaat uit een aantal toestanden en een aantal overgangen en kan een aangeboden woord accepteren of verwerpen.

Voorbeeld

Informeel beschrijven we een eindige automaat met een toestandsdiagram:

Voorbeeld van een eenvoudige eindige automaat

De automaat bestaat uit toestanden. In de figuur zijn dat drie ronde toestanden q₀, q₁ en q₂. Tussen deze toestanden lopen overgangen, dat zijn de pijlen. Verder moet de automaat een begintoestand hebben, dat is toestand q₀. De begintoestand wordt vaak weergegeven met een pijl die erheen wijst en die niet uit een andere toestand komt. Daarnaast heeft een automaat meestal een eindtoestand. Die tekenen we met een dubbele lijn, dus in de figuur is dat toestand q₂.

Een automaat die zo is opgebouwd, accepteert bepaalde woorden. We geven woorden aan de automaat en de automaat probeert ze te accepteren. Als hij het woord accepteert, antwoordt de automaat JA, anders antwoordt hij NEE. Onze automaat probeert woorden te accepteren die uit de letters “a, b, c” bestaan, dus we kunnen proberen het woord “abbc” te accepteren.

We beginnen in de begintoestand q₀ en de invoer is het woord “abbc”. Vanaf nu volgen we de pijlen.

We lezen het woord zoals gewoonlijk van links naar rechts, dus als eerste nemen we het symbool “a”. De pijl voor invoer “a” gaat naar toestand q₁, dus daar gaan we naartoe en we halen het symbool “a” van het woord af. De invoer is nu het woord “bbc”:

De pijl voor invoer “b” wijst terug naar knoop q₁. We halen weer de eerste letter weg en de invoer is nu het woord “bc”. We blijven opnieuw in toestand q₁. Tot slot is de invoer het woord “c”. Vanuit toestand q₁ stuurt de pijl voor invoer “c” ons naar toestand q₂.

We hebben alle letters van het invoerwoord opgebruikt en we zitten in toestand q₂, een eindtoestand. Deze eindige automaat accepteert dus het woord “abbc”.

Als we aan het einde niet in een accepterende toestand zouden zitten, zou de automaat het woord niet accepteren. De automaat accepteert een woord ook niet als we in een bepaalde toestand nergens heen kunnen. Bij de invoer “ab” komen we bijvoorbeeld in toestand q₁ terecht en daar blijven we steken — de automaat accepteert zo'n woord niet. Als we het woord “aabbc” testen, hebben we weer pech, want uit toestand q₁ vertrekt geen pijl voor de letter “a”.

Een eindige automaat dient dus om een bepaalde verzameling woorden te herkennen. In de praktijk zouden we een automaat bijvoorbeeld kunnen gebruiken om te controleren of een invoerwoord een geldig e-mailadres is.

Definitie van een eindige automaat

De voorgaande intuïtieve voorstelling van wat een eindige automaat is, moeten we formaliseren, zodat we beter met automaten kunnen werken.

We zeggen dat een eindige (deterministische) automaat een vijftal ⟨Q, Σ, δ, q₀, F⟩ is, waarbij

Q een eindige verzameling toestanden is,
Σ (hoofdletter sigma) het alfabet is (een eindige verzameling symbolen/letters),
δ: Q × Σ ⟶ Q de overgangsfunctie is,
q₀ ∈ Q de begintoestand is,
F ⊆ Q de verzameling eindtoestanden (accepterende toestanden) is.

Als we teruggaan naar de vorige automaat,

dan kunnen we zeggen dat de verzameling toestanden Q uit drie toestanden bestaat: Q = {q₀, q₁, q₂}. Het alfabet Σ bevat de letters waarmee we woorden kunnen vormen die de automaat vervolgens accepteert of verwerpt. Hier is dat waarschijnlijk het alfabet Σ= {a, b, c}, maar het mag ook een willekeurige bovenverzameling zijn. De begintoestand q₀ is toestand q₀, daar verandert niets aan. De verzameling eindtoestanden bevat bij deze automaat maar één toestand: F = {q₂}.

Met de overgangsfunctie bedoelen we dan die drie pijlen met letters. Als de notatie δ: Q × Σ ⟶ Q je in de war brengt: die betekent alleen dat δ een functie is (of beter gezegd een afbeelding) die twee argumenten neemt: een toestand uit Q en een letter uit Σ. Na aanroep geeft de functie een nieuwe toestand terug. Onze overgangsfunctie zouden we met een tabel zo kunnen definiëren:

$\begin{array}{ccc} Q & Σ & \to Q \\ q_{0} & a & q_{1} \\ q_{1} & b & q_{1} \\ q_{1} & c & q_{2} \end{array}$

Als we dus δ(q₁, c) aanroepen, passen we de derde rij toe en antwoordt de functie met toestand q₂ — net als het diagram. Als we in toestand q₁ zitten en de invoer is de letter “c”, dan komen we in toestand q₂ terecht. Voordat we formeel definiëren wat het betekent dat een automaat een woord accepteert, gebruiken we het intuïtieve begrip en laten we nog een paar voorbeelden zien.

Nog meer voorbeelden

Maak een automaat die werkt over het binaire alfabet, dus Σ= {0, 1}, en alleen woorden accepteert die op een één eindigen. Hij accepteert bijvoorbeeld de woorden 1, 01, 000001, 0101011.

Onze automaat heeft twee toestanden — de begintoestand q₀ en de eindtoestand q₁. Zodra de invoer het cijfer 1 is, gaan we naar de eindtoestand q₁ en blijven we daar. Is de invoer daarentegen het cijfer 0, dan gaan we naar de niet-eindtoestand q₀ en blijven we ook daar.
Construeer een automaat over het binaire alfabet die alleen woorden accepteert waarvan de eerste letter verschilt van de laatste letter.

De automaat splitst zich meteen in de eerste stap in twee “deelautomaten”. Als het woord met een nul begint, gaat de automaat het linkerdeel in en blijft daar; begint het met een één, dan gaat hij naar het rechterdeel. Daarna is het standaard: als we in het linkerdeel zitten en de invoer is 1, gaan we naar de eindtoestand en blijven we daar. Is de invoer 0, dan gaan we naar toestand q₁, die geen eindtoestand is.

In tegenstelling tot de vorige automaten heeft deze automaat meer eindtoestanden, namelijk F = {q₃, q₄}.
Construeer een automaat over het binaire alfabet die alleen woorden accepteert die geen twee nullen achter elkaar bevatten.

Deze automaat is om twee redenen interessant. De eerste is dat hij het lege woord accepteert. We kunnen het lege woord aan de automaat geven en de automaat accepteert het als de begintoestand tegelijk een eindtoestand is, en dat is hier het geval. Omdat het lege woord een woord is dat geen twee nullen achter elkaar bevat, is dat precies goed. De tweede bijzonderheid is dat bij deze automaat alle toestanden eindtoestanden zijn. De automaat accepteert een woord dan alleen niet als er uit een toestand geen overgang vertrekt. Dat gebeurt in toestand q₁, die geen overgang voor 0 heeft, want dan zou het woord twee nullen achter elkaar bevatten.
Construeer een automaat over het alfabet {-,+,.,0,1,…,9} die alleen woorden accepteert die een getal voorstellen. Dat betekent: een geheel getal zoals 2, 548, 98263, of een decimaal getal zoals 5584.48, 3.14, en beide ook met een minteken als negatief getal -2, -548, -3.14, en ook met een expliciet plusteken, dus +2, +548, +3.14. Tegelijk moeten we het getal 0.123 ook kunnen schrijven als .123 (zonder die nul vooraan), inclusief beide tekens. Hier gebruiken we, zoals in programmeertalen, een punt als decimaalteken. We voeren een hulpnotatie in: in plaats van tien overgangen voor tien cijfers uit te schrijven, gebruiken we het symbool N.
Construeer een automaat over het binaire alfabet die alleen woorden accepteert van de vorm 0ⁿ1ⁿ, dat wil zeggen: woorden die beginnen met een bepaald aantal nullen, gevolgd door evenveel enen. Voorbeelden van zulke woorden zijn 0011, 00001111, 01.

Zo'n automaat kan niet worden gebouwd, omdat we het aantal nullen nergens kunnen “onthouden”. We zouden meerdere “deelautomaten” moeten maken, net als in het tweede voorbeeld, maar het zouden er oneindig veel moeten zijn, voor elke waarde van n één.

Formalisering van de berekening van een automaat

We hebben de eindige automaat zelf al formeel gedefinieerd. Nu moeten we nog definiëren wat zo'n automaat eigenlijk doet, dus we definiëren de berekening van een automaat.

Configuratie van een automaat: we zeggen dat een paar ⟨q, w⟩ ∈ Q × Σ^∗ een configuratie van de automaat is, waarbij q de huidige toestand is waarin de automaat zich bevindt en w het nog niet gelezen deel van het woord. Σ^∗ is de afsluiting van het alfabet Σ, de verzameling van alle woorden die uit de letters van het alfabet Σ kunnen worden samengesteld. Het lege woord, dat we aangeven met ε, hoort ook bij de afsluiting.

Als we een automaat ⟨Q, Σ, δ, q₀, F⟩ hebben en een woord w proberen te accepteren, dan bevindt de automaat zich in de beginconfiguratie ⟨q₀, w⟩. Als we teruggaan naar de automaat

en het woord w = abbc willen accepteren, dan is de beginconfiguratie ⟨q₀, abbc⟩.

Een rekenstap definiëren we als een relatie ↦ tussen de verzamelingen (Q × Σ^∗) × (Q × Σ^∗), dus tussen configuraties van de automaat. Laat w = w₀w₁… w_n het nog niet gelezen deel van het woord w voorstellen. Dan zeggen we dat de paren ⟨q₁, w₀w₁… w_n⟩ en ⟨q₂, w₁… w_n⟩ in de relatie ↦ staan, wat we noteren als

$⟨ q_{1}, w_{0} w_{1} \dots w_{n} ⟩ \mapsto ⟨ q_{2}, w_{1} \dots w_{n} ⟩,$

dan en slechts dan als δ(q₁, w₀) = q₂. Terug naar ons voorbeeld: de beginconfiguratie is ⟨q₀, abbc⟩. Uit het diagram zien we dat we bij invoer “a” naar toestand q₁ kunnen gaan. We kunnen dus schrijven

$⟨ q_{0}, a b b c ⟩ \mapsto ⟨ q_{1}, b b c ⟩,$

want er geldt δ(q₀, a) = q₁. Daarmee hebben we één rekenstap gedaan — we hebben gekeken naar welke toestand we bij de gegeven invoer (= de eerste letter van het nog niet gelezen deel van het woord) moeten gaan, zijn daarheen gegaan en hebben de eerste letter van het nog niet gelezen deel van het woord verwijderd. Zo hebben we een nieuwe configuratie gekregen.

De reflexieve en transitieve afsluiting van de relatie rekenstap noteren we als ↦ ^∗. Als we dus K₁ ↦ ^∗ K₂ schrijven, waarbij K₁, K₂ configuraties van de automaat zijn, betekent dat dat we vanuit configuratie K₁ via een aantal rekenstappen in configuratie K₂ kunnen komen, oftewel er bestaat een eindige rij configuraties zodat:

$K_{1} \mapsto K_{11} \mapsto K_{12} \mapsto K_{13} \mapsto \dots \mapsto K_{2}$

In onze automaat geldt bijvoorbeeld ⟨q₀, abbc⟩ ↦ ^∗ ⟨q₁,bc⟩, want na twee rekenstappen houden we het woord “bc” over en blijven we in toestand q₁. Er bestaat dus de volgende rij configuraties:

$⟨ q_{0}, a b b c ⟩ \mapsto ⟨ q_{1}, b b c ⟩ \mapsto ⟨ q_{1}, b c ⟩$

De automaat accepteert het woord w dan en slechts dan als er een q_f ∈ F bestaat zodat $⟨ q_{0}, w ⟩ \mapsto^{*} ⟨ q_{f}, ε ⟩$ Dat betekent dat de automaat het woord w accepteert dan en slechts dan als er een rij rekenstappen bestaat zodat we aan het einde van die rij het hele woord hebben gelezen en ons in een eindtoestand van de automaat bevinden. Dat we het hele woord hebben gelezen, wordt uitgedrukt doordat in de configuratie op de plaats van het woord ε staat, het lege woord. Onze automaat accepteert het woord abbc, omdat de volgende rij configuraties bestaat:

$⟨ q_{0}, a b b c ⟩ \mapsto ⟨ q_{1}, b b c ⟩ \mapsto ⟨ q_{1}, b c ⟩ \mapsto ⟨ q_{1}, c ⟩ \mapsto ⟨ q_{2}, ε ⟩$

en toestand q₂ is een eindtoestand, q₂ ∈ F.

De taal die door een automaat wordt geaccepteerd is de verzameling van alle woorden die de automaat accepteert. De taal van een automaat A noteren we als L(A). Er geldt dus L(A) ⊆ Σ^∗ en

$L (A) = {w \in Σ^{*} | A accepteert het woord w}$

Een reguliere taal is een taal die door een of andere eindige automaat wordt geaccepteerd.

Twee eindige automaten zijn equivalent als ze dezelfde taal accepteren. Dus automaten A₁ en A₂ zijn equivalent als L(A₁) = L(A₂).

Bronnen

Hoofdstukken: Eindige automaat, Totale automaat, Niet-deterministische eindige automaat, Simulatie van een niet-deterministische automaat, Omzetting van NFA naar DFA

« Vorige: Formele talen

Volgende: Totale automaat »