Simulering af en NFA
Hvis vi har en ikke-deterministisk automat og vil finde ud af, om den accepterer et givet ord, kan vi omdanne automaten til en deterministisk, vi kan prøve os frem på en eller anden måde, eller vi kan bruge en algoritme, der simulerer NFA'ens virkemåde.
Algoritmens princip
Princippet viser vi på et velegnet eksempel. Vi ser på denne automat:
Det er en ikke-deterministisk endelig automat, som accepterer et eller andet sprog. Hvilket, behøver vi slet ikke bekymre os om nu. Vi viser, hvordan beregningen i en sådan automat kan forløbe for inputordet 11001. Overvejelsen er den, at vi behandler et symbol fra ordet og ser, hvor vi overalt kan komme hen takket være de flere overgange for det samme symbol. Alle disse tilstande husker vi, og i det næste skridt antager vi, at vi er »i alle disse tilstande samtidig«, og vi interesserer os for, hvor vi videre kan komme hen fra disse tilstande.
Vi husker således mængden af tilstande, som vi kan befinde os i, og den ulæste del af ordet. I begyndelsen har vi derfor parret ⟨{q0}, 11001⟩. Vi begynder i tilstanden q0 (starttilstanden), og inputtet er ordet 11001. Automaten ser sådan ud, den tilstand, vi er i, er fremhævet med rødt og fed skrift:
Det første symbol er 1, fra tilstanden q0 er der kun én overgang for symbolet 1, så vi kommer til tilstanden q1. Vi husker parret ⟨{q1}, 1001⟩. Automaten ser sådan ud:
Vi fortsætter. Den ulæste del af ordet er 1001, så vi leder igen efter overgange for 1. Dem er der nu to af — tilbage til tilstanden q0 og desuden til tilstanden q3. Nu går vi til begge tilstande på samme tid. Vi husker således parret ⟨{q0, q3}, 001⟩.
Hvad er logikken i det? Vi ved, at der findes en vej, hvor vi fra starttilstanden ved hjælp af ordet 11 kommer både til tilstanden q3 og til tilstanden q0. Endnu ved vi ikke, hvilken gren der bliver nyttig for os, så vi husker simpelthen begge. Vi fortsætter. Som input har vi symbolet 0. Nu skal vi se både på overgangene fra q0 og på overgangene fra q3. Fra tilstanden q0 går der overgange til tilstandene q1 og q2, fra tilstanden q3 går der en overgang tilbage til q1. Vi regner alle disse tilstande med og får parret ⟨{q1, q2}, 01⟩:
Men vi er ikke færdige med dette skridt endnu. Vi ser, at der fra tilstanden q2 går en epsilon-overgang til tilstanden q4. Vi ved, at efter en epsilon-overgang kan vi »gå når som helst«, uden at vi læser et yderligere tegn. Med andre ord — uden at vi læser endnu et symbol fra inputordet, kan vi stadig flytte os til tilstanden q4. Vi tilføjer derfor tilstanden q4 til de tilstande, som vi kan befinde os i: ⟨{q1, q2, q4}, 01⟩. Automaten ville vi farvelægge sådan:
Dernæst er inputtet 0. Vi ser, hvor vi kan flytte os hen fra de tre tilstande, vi er i. Fra q1 kan vi ikke flytte os nogen steder, fordi der mangler en overgang for 0. Beregningen i denne gren slutter. Fra tilstanden q4 kommer vi heller ikke nogen steder hen. Fra tilstanden q2 kommer vi tilbage til tilstanden q2. Men da der igen fra tilstanden q2 går en epsilon-overgang til tilstanden q4, kan vi også komme til tilstanden q4. Fra mængden af tilstande {q1, q2, q4} kan vi således for symbolet 0 komme til mængden af tilstande {q2, q4}, og vi får parret ⟨{q2, q4}, 1⟩:
Til sidst har vi symbolet 1 som input. Fra tilstanden q2 kommer vi ingen steder hen, beregningen i denne gren slutter. Fra tilstanden q4 kommer vi derimod til tilstandene q3 og q5. Vi får parret ⟨{q3, q5}, ε⟩:
Automaten har nu læst hele ordet og »befinder sig« i to tilstande: q3, q5. Da mindst én af dem er en accepttilstand, accepterer automaten ordet 11001.
Algoritme
Først har vi brug for en funktion, der får en mængde af tilstande som parameter og beregner, hvilke tilstande vi desuden kan komme til ved hjælp af epsilon-overgange. Input er således automaten ⟨Q, Σ, δ, q0, F⟩ og mængden af tilstande States, og output er en overmængde af disse tilstande, som kan nås ved hjælp af epsilon-overgange. Denne operation kalder vi epsilon-afslutningen af mængden States.
Denne funktion bruger vi i en funktion, der skal simulere den ikke-deterministiske automats virkemåde. Input er automaten, inputordet w = w1w2… wn og mængden af tilstande, som automaten aktuelt befinder sig i. Output er enten svaret Ja eller Nej, alt efter om automaten accepterer eller ikke accepterer det givne ord.
Hvis vi vil kontrollere, om automaten accepterer ordet w, kalder vi funktionen sådan: ComputeNFA(⟨Q, Σ, δ, q0, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q0, F⟩, {q0})).
Kilder
Kapitler: Endelig automat, Total automat, Ikke-deterministisk endelig automat, Simulering af en NFA, Omdannelse af NFA til DFA
