Niet-deterministische eindige automaat

De eindige automaat uit de vorige hoofdstukken (afgekort FA of DFA) was altijd deterministisch, wat zich uitte in het feit dat op elk moment duidelijk was wat de automaat zou doen. Nu kijken we naar het algemenere begrip van niet-deterministische eindige automaten (afgekort NFA), waarin overgangen kunnen bestaan die uit dezelfde toestand vertrekken en bij hetzelfde symbool horen.

Voorbeeld

Kijk naar het volgende diagram van een automaat:

Wat is hier bijzonder aan? Dat er vanuit knoop q₀ twee pijlen voor het symbool 0 vertrekken. Als we proberen het woord 001 te accepteren, lijkt het erop dat de automaat niet weet of hij in toestand q₀ moet blijven of de overgang naar q₁ moet volgen. Zo'n automaat is niet-deterministisch.

Determinisme betekent in deze context dat in elke situatie duidelijk is wat de automaat doet; er is geen ruimte voor dubbelzinnigheid. Een deterministische automaat heeft voor elke toestand en elk symbool maar één overgang. Niet-determinisme betekent dubbelzinnigheid — vanuit één toestand kunnen voor hetzelfde symbool bijvoorbeeld drie overgangen vertrekken.

En hoe kiest de automaat dan? Een niet-deterministische automaat kiest altijd (soms zeggen we ook: “raadt”) de overgang die ertoe leidt dat het woord wordt geaccepteerd, als dat mogelijk is.

Als we het woord 001 aan de automaat geven, heeft de automaat de volgende mogelijkheden om het woord te verwerken:

$\begin{array}{r} q_{0} \to q_{0} \to q_{0} \to q_{0} \\ q_{0} \to q_{0} \to q_{1} \to q_{2} \end{array}$

plus mogelijkheden waarbij hij niet het hele woord leest. In de eerste blijft hij steeds in toestand q₀, wat zeker mag, de overgangsregels staan het toe. In de tweede tak waagt hij zich naar andere toestanden en uiteindelijk komt hij in toestand q₂, een eindtoestand. In deze tak zou de automaat het woord accepteren. Een niet-deterministische automaat kiest automatisch altijd de tak waarin hij het woord accepteert, als zo'n tak bestaat.

Hoe kiest hij automatisch die “gunstige” tak? We kunnen het ons zo voorstellen dat de niet-deterministische automaat alle mogelijke takken doorloopt, en als hij een tak vindt waarin hij het woord accepteert, accepteert hij het woord. Hoe zou hij alle takken kunnen doorlopen? Heel simpel: op het moment dat hij in een toestand zit waaruit voor het huidige symbool n pijlen vertrekken, kopieert de automaat zichzelf n keer en gaat elke kopie een andere weg. Zo doorlopen we stap voor stap alle mogelijkheden.

Boomweergave van de berekening van een automaat

We passen de vorige automaat een beetje aan:

Het niet-determinisme blijft in de eerste toestand. De vorige automaat accepteerde alle woorden die op 01 eindigen. Deze aangepaste automaat accepteert alle woorden die het deelwoord 01 bevatten. Hij accepteert dus bijvoorbeeld het woord 101 of 0101. Alle takken van de berekening kunnen we eenvoudig visualiseren met een boom, bijvoorbeeld voor het woord 01010 zou de boom er zo uit kunnen zien:

Aan het begin zitten we in de begintoestand q₀. De invoer is het woord 01010, het eerste nog niet gelezen teken is 0. Vanuit toestand q₀ vertrekken twee overgangen voor het symbool 0, naar de toestanden q₀ en q₁. De boom heeft in deze knoop dus twee kinderen: q₀ en q₁. Vervolgens lezen we het symbool 1. Daar is geen dubbelzinnigheid, we gaan naar de toestanden q₀ en q₂. Daarna lezen we het teken 0. In de linkertak ontstaat opnieuw dubbelzinnigheid, we splitsen de berekening in twee nieuwe takken. In de ene blijven we weer in q₀ en in de andere gaan we naar q₁. En zo verder.

Merk op dat in totaal twee takken eindigen in toestand q₂, in een eindtoestand. Er bestaan dus twee takken van de berekening waarmee de automaat het gegeven woord kan accepteren. Deze automaat zou het woord 01010 dus accepteren. We kunnen proberen een vergelijkbare boom te maken voor het woord 1000.

De berekening blijft ofwel in toestand q₀ of gaat naar toestand q₁, maar vanaf daar kan hij nergens meer heen, omdat de invoer nu alleen nog nullen bevat en toestand q₁ alleen een overgang voor het symbool 1 heeft. Geen enkele tak van de berekening eindigt in een eindtoestand, dus de automaat accepteert het woord 1000 niet.

Epsilonovergangen

In niet-deterministische automaten mogen we bovendien epsilonovergangen gebruiken. Dat zijn overgangen die we kunnen maken ongeacht welk symbool er op de invoer staat, en zonder dat we een symbool van het woord lezen. Hoe zouden we een niet-deterministische automaat kunnen maken die het lege woord accepteert, alle woorden die alleen uit enen bestaan en woorden van de vorm (10)ⁿ, dus 10, 1010, …?

We hebben de automaat in twee “deelautomaten” gesplitst. De bovenste zorgt ervoor dat hij woorden herkent die uit enen bestaan, de onderste zorgt voor woorden van de vorm (10)ⁿ. We proberen het woord 111 te accepteren. De automaat zit aan het begin in toestand q₀ en heeft het woord 111 als invoer. Omdat hij epsilonovergangen tot zijn beschikking heeft, kan hij besluiten naar toestand q₁ of q₂ te gaan, al naargelang het hem uitkomt. We zien dat het hem uitkomt om naar toestand q₁ te gaan. De automaat gaat daarheen. Daarbij heeft hij als invoer nog steeds het woord 111! Pas op dit moment begint hij symbolen van het woord te lezen en van toestand q₁ weer naar q₁ te gaan, tot hij het hele woord heeft gelezen en accepteert.

Als we 1010 zouden proberen te accepteren, zou de automaat aan het begin naar toestand q₂ gaan en pas vanaf daar symbolen verwerken, en ook dan zou hij het woord accepteren.

Bij het woord 1100 zou de automaat kunnen doen wat hij wil, hij kan dat woord op geen enkele manier accepteren.

Epsilonovergangen en niet-determinisme maken het werk in veel opzichten makkelijker. Het bewijs dat de vereniging van reguliere talen weer een reguliere taal is, kan met epsilonovergangen bijvoorbeeld veel eenvoudiger worden opgeschreven dan in het geval van deterministische eindige automaten. In dat bewijs hadden we voorbeelden van de volgende automaten

en vervolgens hebben we een deterministische eindige automaat geconstrueerd die de vereniging van beide talen accepteerde. Met epsilonovergangen kunnen we zo'n automaat als volgt opbouwen:

We voegen gewoon een nieuwe begintoestand toe, daaruit vertrekken twee epsilonovergangen naar de oorspronkelijke begintoestanden van de oorspronkelijke automaten, en dat is alles. De automaat besluit niet-deterministisch of hij het woord met de ene of met de andere “deelautomaat” probeert te accepteren.

Definitie van een niet-deterministische automaat

We hebben al laten zien waarin een deterministische en een niet-deterministische eindige automaat verschillen; we hoeven dat alleen nog te formaliseren. Een deterministische eindige automaat hebben we gedefinieerd als een vijftal ⟨Q, Σ, δ, q₀, F⟩, waarbij Q de verzameling toestanden is, Σ het alfabet, δ de overgangsfunctie, q₀ de begintoestand en F de verzameling eindtoestanden. Het enige wat in de definitie van niet-deterministische automaten verandert, is de definitie van de overgangsfunctie.

In de deterministische versie kon de functie bij de aanroep δ(q, w) maar één toestand teruggeven, terwijl ze in de niet-deterministische versie meerdere toestanden kan teruggeven — als er voor één symbool meer overgangen zijn gedefinieerd. Omdat we ook epsilonovergangen moeten definiëren, geven we de verzameling Σ ∪ {ε} de naam Σ_ε, dus Σ_ε = Σ ∪ {ε}. De functie δ definiëren we dan als

$δ : Q \times Σ_{ε} \to 2^{Q}$

Die 2^Q is de machtsverzameling, de verzameling van alle deelverzamelingen van de verzameling Q. De formalisering van de berekening lijkt sterk op die bij eindige automaten. Een configuratie van de automaat is weer een paar ⟨q, w⟩ ∈ Q × Σ^∗. Een rekenstap ↦ is een relatie op de verzameling configuraties zodat

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

dan en slechts dan als q_j ∈ δ(q_i, w₀). In deze zin zat het grootste verschil. Bij deterministische automaten hadden we deze voorwaarde geschreven als q_j = δ(q_i, w₀), omdat de functie δ altijd één toestand teruggaf. De niet-deterministische versie van de overgangsfunctie geeft een verzameling toestanden terug, daarom staat er het symbool ∈. De reflexieve en transitieve afsluiting van de relatie noteren we weer als ↦ ^∗. We zeggen dat de automaat het woord w accepteert dan en slechts dan als er een q_f ∈ F bestaat zodat

$⟨ q_{0}, w ⟩ \mapsto^{*} ⟨ q_{f}, ε ⟩ .$

Bronnen

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

« Vorige: Totale automaat

Volgende: Simulatie van een niet-deterministische automaat »