Simulering av ikke-deterministisk automat

Hvis vi har en ikke-deterministisk automat og vil finne ut om den aksepterer et gitt ord, kan vi omforme automaten til en deterministisk, vi kan prøve oss fram på en eller annen måte, eller vi kan bruke en algoritme som simulerer virkemåten til NFA-en.

Prinsippet bak algoritmen

Prinsippet viser vi best på et passende eksempel. La oss ha denne automaten:

Dette er en ikke-deterministisk endelig automat som aksepterer et språk. Hvilket, trenger vi overhodet ikke å bry oss om nå. Vi skal vise hvordan beregningen i en slik automat kan se ut for inputordet 11001. Tanken er at vi behandler ett symbol fra ordet og ser hvor vi kan gå på grunn av flere overganger for samme symbol. Vi husker alle disse tilstandene, og i neste steg antar vi at vi er «i alle disse tilstandene samtidig», og vi er interessert i hvor vi kan komme videre fra disse tilstandene.

Vi husker altså en mengde av tilstander vi kan befinne oss i, og den delen av ordet som ikke er lest. I begynnelsen har vi derfor paret ⟨{q₀}, 11001⟩. Vi begynner i tilstanden q₀ (starttilstanden), og input er ordet 11001. Automaten ser slik ut, og tilstanden vi er i, er uthevet med rødt og fet skrift:

Det første symbolet er 1, og fra tilstanden q₀ går det bare én overgang for symbolet 1, så vi kommer til tilstanden q₁. Vi husker paret ⟨{q₁}, 1001⟩. Automaten ser slik ut:

Vi fortsetter. Den delen av ordet som ikke er lest, er 1001, så vi leter igjen etter overganger for 1. Nå er det to — tilbake til tilstanden q₀ og videre til tilstanden q₃. Vi går nå til begge tilstandene samtidig. Vi husker altså paret ⟨{q₀, q₃}, 001⟩.

Hva er logikken i dette? Vi vet at det finnes en vei fra starttilstanden som med ordet 11 tar oss både til tilstanden q₃ og til tilstanden q₀. Ennå vet vi ikke hvilken gren som kommer til å passe, så vi husker rett og slett begge. Vi fortsetter. Nå har vi symbolet 0 som input. Nå må vi se både på overgangene fra q₀ og på overgangene fra q₃. Fra tilstanden q₀ går det overganger til tilstandene q₁ og q₂, og fra tilstanden q₃ går det en overgang tilbake til q₁. Vi tar med alle disse tilstandene, og da får vi paret ⟨{q₁, q₂}, 01⟩:

Men vi er ikke ferdige med dette steget ennå. Vi ser at det fra tilstanden q₂ går en epsilonovergang til tilstanden q₄. Vi vet at vi kan «gå når som helst» etter en epsilonovergang uten å lese noe tegn til. Med andre ord — uten å lese et nytt symbol fra inputordet kan vi også flytte oss til tilstanden q₄. Vi legger derfor tilstanden q₄ til blant tilstandene vi kan befinne oss i: ⟨{q₁, q₂, q₄}, 01⟩. Automaten ville vi farget slik:

Videre er input 0. Vi ser på hvor vi kan flytte oss fra de tre tilstandene vi er i. Fra q₁ kan vi ikke flytte oss noen steder, for overgangen for 0 mangler. Beregningen i denne grenen slutter. Fra tilstanden q₄ kommer vi heller ikke noen steder. Fra tilstanden q₂ kommer vi tilbake til tilstanden q₂. Men siden det igjen går en epsilonovergang fra tilstanden q₂ til tilstanden q₄, kan vi også komme til tilstanden q₄. Fra mengden av tilstander {q₁, q₂, q₄} kan vi altså for symbolet 0 komme til mengden av tilstander {q₂, q₄}, og vi får paret ⟨{q₂, q₄}, 1⟩:

Til slutt har vi symbolet 1 som input. Fra tilstanden q₂ kommer vi ingen steder, og beregningen i denne grenen slutter. Fra tilstanden q₄ kommer vi derimot til tilstandene q₃ og q₅. Vi får paret ⟨{q₃, q₅}, ε⟩:

Automaten har nå lest hele ordet og «befinner seg» i to tilstander: q₃, q₅. Siden minst én av dem er en sluttilstand, aksepterer automaten ordet 11001.

Algoritmen

Først trenger vi en funksjon som tar en mengde av tilstander som parameter og regner ut hvilke tilstander vi i tillegg kan komme til ved hjelp av epsilonoverganger. Input er altså automaten ⟨Q, Σ, δ, q₀, F⟩ og mengden av tilstander States, og output er en supermengde av disse tilstandene, der vi kan komme til ved hjelp av epsilonoverganger. Denne operasjonen kaller vi epsilontillukningen av mengden 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}$

Denne funksjonen bruker vi i funksjonen som skal simulere virkemåten til den ikke-deterministiske automaten. Input er automaten, inputordet w = w₁w₂… w_n og mengden av tilstander automaten befinner seg i akkurat nå. Output er enten svaret YES eller NO, alt etter om automaten aksepterer det gitte ordet eller ikke.

$\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}$

Hvis vi vil sjekke om automaten aksepterer ordet w, kaller vi funksjonen slik: ComputeNFA(⟨Q, Σ, δ, q₀, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q₀, F⟩, {q₀})).

Kilder

Kapitler: Endelig automat, Total automat, Ikke-deterministisk endelig automat, Simulering av ikke-deterministisk automat, Omforming av NFA til DFA

« Forrige: Ikke-deterministisk endelig automat

Neste: Omforming av NFA til DFA »