Ikke-deterministisk endelig automat

Endelig automat slik den ble presentert i de forrige kapitlene (forkortet DFA) var alltid deterministisk, og det viste seg ved at det i hvert øyeblikk var klart hva automaten ville gjøre. Nå ser vi på det mer generelle begrepet ikke-deterministiske endelige automater (forkortet NFA), der det kan finnes overganger som går ut fra samme tilstand og gjelder samme symbol.

Eksempel

Se på følgende diagram av en automat:

Hva er spesielt med den? At det fra noden q₀ går to kanter for symbolet 0. Hvis vi prøver å akseptere ordet 001, ser det ut til at automaten ikke vil vite om den skal bli i tilstanden q₀ eller om den skal følge overgangen til q₁. En slik automat ville være ikke-deterministisk.

Determinisme betyr i denne sammenhengen at det i hver situasjon er klart hva automaten gjør, og at det ikke er rom for tvetydighet. En deterministisk automat har bare én overgang for hver tilstand og hvert symbol. Ikke-determinisme betyr tvetydighet — fra én tilstand kan det for eksempel gå tre overganger for samme symbol.

Hvordan bestemmer automaten seg da? En ikke-deterministisk automat velger alltid (noen ganger sier vi også at den «gjetter») den overgangen som fører til at ordet blir akseptert, hvis det er mulig.

Hvis vi sender ordet 001 inn i automaten, har automaten disse mulighetene for å behandle ordet:

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

pluss mulighetene der den ikke leser hele ordet. I den første blir den hele tiden i tilstanden q₀, og det kan den helt sikkert, siden overgangsreglene tillater det. I den andre grenen våget den seg videre til andre tilstander og kom til slutt til tilstanden q₂, som er en sluttilstand. I denne grenen ville automaten akseptere ordet. En ikke-deterministisk automat velger alltid automatisk den grenen der den aksepterer ordet, hvis en slik gren finnes.

Hvordan klarer den å velge den «gunstige» grenen automatisk? Vi kan tenke oss at den ikke-deterministiske automaten går gjennom alle mulige grener, og hvis den finner en gren der den aksepterer ordet, aksepterer den ordet. Hvordan kunne den gå gjennom alle grenene? Når den er i en tilstand der det for gjeldende symbol går n kanter ut, kopierer automaten rett og slett seg selv n ganger, og hver kopi går sin vei. Slik går vi etter hvert gjennom alle mulighetene.

Trerepresentasjon av automatens beregning

Vi endrer den forrige automaten litt:

Ikke-determinismen blir værende i den første tilstanden. Den forrige automaten aksepterte alle ord som slutter på 01. Denne endrede automaten aksepterer alle ord som inneholder delordet 01. Den aksepterer altså for eksempel ordet 101 eller 0101. Alle grenene i beregningen kan vi lett visualisere ved hjelp av et tre, for ordet 01010 kunne treet for eksempel se slik ut:

I begynnelsen er vi i starttilstanden q₀. Som input har vi ordet 01010, og det første tegnet som ikke er lest, er 0. Fra tilstanden q₀ går det to overganger for symbolet 0, til tilstandene q₀ og q₁. Treet får altså to barn i denne noden: q₀ og q₁. Videre leser vi symbolet 1. Der er det ingen tvetydighet, vi flytter oss til tilstandene q₀ og q₂. Videre leser vi tegnet 0, og i den venstre grenen oppstår det igjen tvetydighet, så vi deler beregningen i to nye grener. I den ene blir vi igjen i q₀, og i den andre går vi til q₁. Og så videre.

Legg merke til at til sammen to grener ender i tilstanden q₂, altså i sluttilstanden. Det finnes to grener i beregningen der automaten kan akseptere det gitte ordet. Denne automaten ville altså akseptere ordet 01010. Vi kan prøve å lage et tilsvarende tre for ordet 1000.

Beregningen blir enten værende i tilstanden q₀ eller går over til tilstanden q₁, men derfra har den ingen steder å gå videre, for input er nå bare nuller, og tilstanden q₁ har bare en overgang for symbolet 1. Ingen gren i beregningen ender i en sluttilstand, så automaten aksepterer ikke ordet 1000.

Epsilonoverganger

I ikke-deterministiske automater kan vi i tillegg bruke epsilonoverganger. Det er overganger vi kan utføre uansett hvilket symbol som er input, og uten å lese noe symbol fra ordet. Hvordan kunne vi skrive en ikke-deterministisk automat som aksepterer det tomme ordet, alle ord som bare består av enere, og ord på formen (10)ⁿ, altså 10, 1010, …?

Vi har delt automaten i to «delautomater». Den øverste sørger for å gjenkjenne ord som består av 1, den nederste tar seg av ord på formen (10)ⁿ. Vi prøver å akseptere ordet 111. I begynnelsen befinner automaten seg i tilstanden q₀ og har ordet 111 som input. Siden den har epsilonoverganger til rådighet, kan den bestemme seg for å gå over til tilstanden q₁ eller q₂, alt etter hva som passer. Vi ser at det passer å gå over til tilstanden q₁. Automaten går dit. Samtidig har den fortsatt ordet 111 som input! Først nå begynner den å lese symboler fra ordet og gå fra tilstanden q₁ til q₁ igjen, til den har lest hele ordet og aksepterer det.

Hvis vi prøvde å akseptere 1010, ville automaten først gå over til tilstanden q₂, og først derfra begynne å behandle symbolene og igjen akseptere ordet.

For ordet 1100 kunne automaten gjøre hva som helst, den har ingen måte å akseptere et slikt ord på.

Epsilonoverganger og ikke-determinisme gjør arbeidet vårt mye lettere. Beviset for at unionen av regulære språk igjen er et regulært språk, kan for eksempel skrives mye enklere med epsilonoverganger enn i tilfellet med deterministiske endelige automater. I det beviset hadde vi eksempler på disse automatene

og dessuten konstruerte vi en endelig deterministisk automat som aksepterte unionen av de to språkene. Med epsilonoverganger kan vi sette sammen en slik automat slik:

Vi legger rett og slett til en ny starttilstand, fra den går det to epsilonoverganger til de opprinnelige starttilstandene i de opprinnelige automatene, og det er alt. Automaten bestemmer seg ikke-deterministisk for om den prøver å akseptere ordet med den ene eller den andre «delautomaten».

Definisjon av ikke-deterministisk automat

Vi har allerede vist hva som skiller en deterministisk og en ikke-deterministisk endelig automat, det gjenstår bare å formalisere det. En deterministisk endelig automat definerte vi som et femtuppel ⟨Q, Σ, δ, q₀, F⟩, der Q er mengden av tilstander, Σ er alfabetet, δ er overgangsfunksjonen, q₀ er starttilstanden og F er mengden av sluttilstander. Det eneste som endrer seg i definisjonen av ikke-deterministiske automater, er definisjonen av overgangsfunksjonen.

I den deterministiske versjonen kunne funksjonen for kallet δ(q, w) bare returnere én tilstand, mens den i den ikke-deterministiske versjonen kan returnere flere tilstander — hvis det er definert flere overganger for ett symbol. Siden vi også må definere epsilonoverganger, betegner vi mengden Σ ∪ {ε} som mengden Σ_ε, altså Σ_ε = Σ ∪ {ε}. Funksjonen δ definerer vi altså som

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

Her betegner 2^Q potensmengden, mengden av alle delmengder av mengden Q. Formaliseringen av beregningen er veldig lik den for endelige automater. En konfigurasjon av automaten er igjen et par ⟨q, w⟩ ∈ Q × Σ^∗. Beregningssteget ↦ er en relasjon på mengden av konfigurasjoner slik at

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

hvis og bare hvis q_j ∈ δ(q_i, w₀). I denne setningen lå den største forskjellen. I deterministiske automater hadde vi denne betingelsen skrevet som q_j = δ(q_i, w₀), siden funksjonen δ alltid returnerte én tilstand. Den ikke-deterministiske versjonen av overgangsfunksjonen returnerer en mengde tilstander, og derfor står symbolet ∈ der. Den refleksive og transitive tillukningen av relasjonen betegner vi igjen ↦ ^∗. Vi sier at automaten aksepterer ordet w hvis og bare hvis det finnes en q_f ∈ F slik at

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

Kilder

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

« Forrige: Total automat

Neste: Simulering av ikke-deterministisk automat »