Simulering av en icke-deterministisk automat

När vi har en icke-deterministisk automat och vill ta reda på om den accepterar ett visst ord kan vi omvandla automaten till en deterministisk, vi kan pröva oss fram på något sätt, eller så kan vi använda en algoritm som simulerar hur en NFA arbetar.

Algoritmens princip

Vi visar principen med ett lämpligt exempel. Låt oss ta den här automaten:

Det är en icke-deterministisk ändlig automat som accepterar något språk. Vi behöver inte alls bry oss om vilket. Vi ska se hur beräkningen i en sådan automat kan se ut för ordet 11001. Tanken är att vi läser en symbol i ordet och tittar på alla tillstånd som vi kan komma till tack vare flera övergångar för samma symbol. Vi kommer ihåg alla dessa tillstånd, och i nästa steg utgår vi från att vi befinner oss ”i alla dessa tillstånd samtidigt” och undersöker vart vi kan komma härifrån.

Vi kommer alltså ihåg en mängd tillstånd som vi kan befinna oss i, och den del av ordet som ännu inte är läst. I början har vi därför paret ⟨{q₀}, 11001⟩. Vi börjar i tillståndet q₀ (starttillståndet) och indata är ordet 11001. Automaten ser ut så här, där tillståndet vi befinner oss i är markerat med rött och fetstil:

Den första symbolen är 1. Från q₀ finns bara en övergång för symbolen 1, så vi kommer till q₁. Vi kommer ihåg paret ⟨{q₁}, 1001⟩. Automaten ser ut så här:

Vi fortsätter. Den olästa delen av ordet är 1001, så vi söker återigen övergångar för 1. Nu finns det två: tillbaka till q₀ och vidare till q₃. Vi går nu till båda tillstånden samtidigt. Vi kommer alltså ihåg paret ⟨{q₀, q₃}, 001⟩.

Vad är logiken i det här? Vi vet att det finns en väg från starttillståndet som med ordet 11 leder både till q₃ och till q₀. Ännu vet vi inte vilken gren som kommer att behövas, så vi kommer helt enkelt ihåg båda. Vi fortsätter. Nästa symbol i indata är 0. Nu måste vi titta på övergångarna både från q₀ och från q₃. Från q₀ går övergångar till q₁ och q₂, och från q₃ går en övergång tillbaka till q₁. Vi tar med alla dessa tillstånd och får paret ⟨{q₁, q₂}, 01⟩:

Vi är dock inte klara med det här steget. Vi ser att det går en epsilonövergång från q₂ till q₄. Vi vet att vi kan ”gå längs” en epsilonövergång när som helst utan att läsa något mer tecken. Med andra ord kan vi flytta oss till q₄ utan att läsa nästa symbol i indata. Vi lägger därför till q₄ bland de tillstånd som vi kan befinna oss i: ⟨{q₁, q₂, q₄}, 01⟩. Automaten skulle vi färglägga så här:

Därefter är nästa symbol i indata 0. Vi tittar på vart vi kan flytta oss från de tre tillstånden som vi befinner oss i. Från q₁ kan vi inte flytta oss någonstans, eftersom övergången för 0 saknas. Beräkningen i den grenen tar slut. Inte heller från q₄ kommer vi någonstans. Från q₂ kommer vi tillbaka till q₂. Men eftersom det återigen går en epsilonövergång från q₂ till q₄ kan vi också komma till q₄. Från mängden av tillstånd {q₁, q₂, q₄} kan vi alltså för symbolen 0 komma till mängden {q₂, q₄}, och vi får paret ⟨{q₂, q₄}, 1⟩:

Till sist har vi symbolen 1 i indata. Från q₂ kommer vi ingenstans, och beräkningen i den grenen tar slut. Från q₄ kommer vi däremot till tillstånden q₃ och q₅. Vi får paret ⟨{q₃, q₅}, ε⟩:

Automaten har nu läst hela ordet och ”befinner sig” i två tillstånd: q₃, q₅. Eftersom minst ett av dem är ett sluttillstånd accepterar automaten ordet 11001.

Algoritmen

Först behöver vi en funktion som tar en mängd tillstånd som parameter och beräknar vilka tillstånd vi dessutom kan komma till med hjälp av epsilonövergångar. Indata är alltså en automat ⟨Q, Σ, δ, q₀, F⟩ och en mängd tillstånd States, och utdata är en övermängd av dessa tillstånd som innehåller de tillstånd som kan nås med epsilonövergångar. Den här operationen kallar vi epsilonslutningen av mängden 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}$

Den här funktionen använder vi i en funktion som simulerar hur en icke-deterministisk automat arbetar. Indata är automaten, ett indataord w = w₁w₂… w_n och den mängd tillstånd som automaten för tillfället befinner sig i. Utdata är antingen svaret Ja eller Nej, beroende på om automaten accepterar ordet eller inte.

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

Om vi vill kontrollera om automaten accepterar ordet w anropar vi funktionen så här: ComputeNFA(⟨Q, Σ, δ, q₀, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q₀, F⟩, {q₀})).

Källor

Kapitel: Ändlig automat, Total automat, Icke-deterministisk ändlig automat, Simulering av en icke-deterministisk automat, Omvandling av NFA till DFA

« Föregående: Icke-deterministisk ändlig automat

Nästa: Omvandling av NFA till DFA »