Simulatie van een niet-deterministische automaat

Als we een niet-deterministische automaat hebben en willen weten of hij een gegeven woord accepteert, kunnen we de automaat omzetten naar een deterministische, we kunnen het op de gok proberen, of we kunnen een algoritme gebruiken dat de werking van de NFA simuleert.

Principe van het algoritme

Het principe laten we zien aan een geschikt voorbeeld. Neem deze automaat:

Dit is een niet-deterministische eindige automaat die een bepaalde taal accepteert. Welke taal, hoeft ons nu helemaal niet te interesseren. We laten zien hoe de berekening van zo'n automaat voor het invoerwoord 11001 eruit kan zien. De gedachtegang is als volgt: we verwerken een symbool van het woord en kijken waar we overal heen kunnen gaan dankzij meerdere overgangen voor hetzelfde symbool. Al die toestanden onthouden we en in de volgende stap gaan we ervan uit dat we “in al die toestanden tegelijk zitten”, en we kijken vanuit die toestanden verder waar we heen kunnen.

We onthouden dus een verzameling toestanden waarin we ons kunnen bevinden, en het nog niet gelezen deel van het woord. Aan het begin hebben we dus het paar ⟨{q₀}, 11001⟩. We beginnen in toestand q₀ (de begintoestand) en de invoer is het woord 11001. De automaat ziet er zo uit; rood en vet is de toestand waarin we zitten:

Het eerste symbool is 1. Vanuit toestand q₀ is er maar één overgang voor het symbool 1, dus we komen in toestand q₁. We onthouden het paar ⟨{q₁}, 1001⟩. De automaat ziet er zo uit:

We gaan verder. Het nog niet gelezen deel van het woord is 1001, dus we zoeken weer overgangen voor 1. Dat zijn er nu twee — terug naar toestand q₀ en naar toestand q₃. We gaan nu naar beide toestanden tegelijk. We onthouden dus het paar ⟨{q₀, q₃}, 001⟩.

Wat is hier de logica van? We weten dat er een pad bestaat om met het woord 11 vanuit de begintoestand zowel in toestand q₃ als in toestand q₀ te komen. We weten nog niet welke tak ons van pas komt, dus onthouden we er gewoon allebei. We gaan verder. De invoer is het symbool 0. Nu moeten we zowel naar de overgangen vanuit q₀ kijken als naar de overgangen vanuit q₃. Vanuit toestand q₀ lopen overgangen naar de toestanden q₁ en q₂, vanuit toestand q₃ loopt een overgang terug naar q₁. We nemen al deze toestanden mee, zodat we het paar ⟨{q₁, q₂}, 01⟩ krijgen:

In deze stap zijn we echter nog niet klaar. We zien dat vanuit toestand q₂ een epsilonovergang naar toestand q₄ loopt. We weten dat we een epsilonovergang “op elk moment kunnen nemen”, zonder een volgend teken te lezen. Met andere woorden: zonder een volgend symbool van het invoerwoord te lezen, kunnen we nog naar toestand q₄ gaan. We voegen toestand q₄ dus toe aan de toestanden waarin we ons kunnen bevinden: ⟨{q₁, q₂, q₄}, 01⟩. De automaat zouden we zo kleuren:

Vervolgens is de invoer 0. We kijken waar we heen kunnen vanuit die drie toestanden waarin we zitten. Vanuit q₁ kunnen we nergens heen, want er ontbreekt een overgang voor 0. De berekening in deze tak eindigt. Vanuit toestand q₄ komen we ook nergens. Vanuit toestand q₂ komen we terug in toestand q₂. Maar omdat vanuit toestand q₂ weer een epsilonovergang naar toestand q₄ loopt, kunnen we ook in toestand q₄ komen. Vanuit de verzameling toestanden {q₁, q₂, q₄} komen we met het symbool 0 dus in de verzameling toestanden {q₂, q₄}, en we krijgen het paar ⟨{q₂, q₄}, 1⟩:

Tot slot is de invoer het symbool 1. Vanuit toestand q₂ komen we nergens, de berekening in deze tak eindigt. Vanuit toestand q₄ komen we echter in de toestanden q₃ en q₅. We krijgen het paar ⟨{q₃, q₅}, ε⟩:

De automaat heeft nu het hele woord gelezen en “bevindt zich” in twee toestanden: q₃, q₅. Omdat minstens één daarvan een eindtoestand is, accepteert de automaat het woord 11001.

Algoritme

Eerst hebben we een functie nodig die als parameter een verzameling toestanden neemt en berekent in welke toestanden we met behulp van epsilonovergangen nog kunnen komen. De invoer is dus een automaat ⟨Q, Σ, δ, q₀, F⟩ en een verzameling toestanden States, en de uitvoer is een bovenverzameling van deze toestanden, waarin we met behulp van epsilonovergangen kunnen komen. Deze bewerking noemen we de epsilonafsluiting van de verzameling States.

$\begin{aligned} Function E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, S t a t e s) \\ N e x t S t a t e s \leftarrow \emptyset \\ ForEach q \in S t a t e s Do \\ N e x t S t a t e s \leftarrow N e x t S t a t e s \cup {q} \cup δ (q, ε) \\ EndFor \\ If N e x t S t a t e s ∖ S t a t e s = \emptyset Do \\ Return S t a t e s \\ Else \\ Return E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, N e x t S t a t e s) \\ EndIf \\ EndFunction \end{aligned}$

Deze functie gebruiken we in de functie die de werking van een niet-deterministische automaat simuleert. De invoer is de automaat, het invoerwoord w = w₁w₂… w_n en de verzameling toestanden waarin de automaat zich op dat moment bevindt. De uitvoer is het antwoord Ja of Nee, al naargelang de automaat het gegeven woord accepteert of niet.

$\begin{aligned} Function C o m p u t e N F A (⟨ Q, Σ, δ, q_{0}, F ⟩, w, S t a t e s) \\ If w = ϵ Do \\ If S t a t e s \cap F \neq \emptyset Do \\ Return YES \\ Else \\ Return NO \\ EndIf \\ EndIf \\ N e x t S t a t e s \leftarrow \emptyset \\ ForEach q \in S t a t e s Do \\ N e x t S t a t e s \leftarrow N e x t S t a t e s \cup δ (q, w_{1}) \\ EndFor \\ N e x t S t a t e s \leftarrow E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, N e x t S t a t e s) \\ Return C o m p u t e N F A (⟨ Q, Σ, δ, q_{0}, F ⟩, w_{2} w_{3} \dots w_{n}, N e x t S t a t e s) \\ EndFunction \end{aligned}$

Als we willen controleren of de automaat het woord w accepteert, roepen we de functie zo aan: ComputeNFA(⟨Q, Σ, δ, q₀, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q₀, F⟩, {q₀})).

Bronnen

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

« Vorige: Niet-deterministische eindige automaat

Volgende: Omzetting van NFA naar DFA »