Ikke-deterministisk endelig automat

Den endelige automat, som blev introduceret i de foregående afsnit (vi forkorter den DFA), var altid deterministisk, hvilket viste sig ved, at det på ethvert tidspunkt var klart, hvad automaten gør. Nu ser vi på det mere almene begreb ikke-deterministiske endelige automater (vi forkorter dem NFA), hvor der kan findes overgange, som udgår fra samme tilstand og er for det samme symbol.

Eksempel

Se på det følgende automatdiagram:

Hvad er mærkeligt ved det? At der fra knuden q₀ går to kanter for symbolet 0. Hvis vi forsøger at acceptere ordet 001, ser det ud til, at automaten ikke ved, om den skal blive i tilstanden q₀, eller om den skal følge overgangen til q₁. En sådan automat ville være ikke-deterministisk.

Determinisme betyder i denne forstand, at det i enhver situation er klart, hvad automaten gør, der er ikke plads til tvetydighed. En deterministisk automat har for hver tilstand og hvert symbol kun én overgang. Ikke-determinisme betyder tvetydighed — fra én tilstand kan der for det samme symbol gå for eksempel tre overgange.

Og hvordan beslutter automaten sig så? En ikke-deterministisk automat vælger altid (nogle gange siger vi også »gætter«) den overgang, der fører til, at den accepterer ordet; hvis det er muligt.

Hvis vi giver automaten ordet 001, har automaten disse muligheder for at 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}$$

plus de muligheder, hvor den ikke læser hele ordet. I den første blev den hele tiden i tilstanden q₀, hvilket den bestemt kan, overgangsreglerne tillader det. I den anden gren turde den gå videre til andre tilstande og nåede til sidst til tilstanden q₂, som er accepterende. I denne gren ville automaten acceptere ordet. En ikke-deterministisk automat vælger automatisk den gren, hvor den accepterer ordet, hvis en sådan gren findes.

Hvordan kan den automatisk vælge den »gunstige« gren? Vi kan forestille os det sådan, at den ikke-deterministiske automat gennemgår alle mulige grene, og hvis den finder en gren, hvor den accepterer ordet, så accepterer den ordet. Hvordan kunne den gennemgå alle grene? Når den er i en tilstand, hvorfra der for det aktuelle symbol går n kanter, kopierer automaten sig selv n gange, og hver kopi går en anden vej. Dermed gennemgår vi efterhånden alle muligheder.

Trærepræsentation af automatens beregning

Vi ændrer den foregående automat en smule:

Ikke-determinismen bliver i den første tilstand. Den foregående automat accepterede alle ord, der ender på 01. Denne ændrede automat accepterer alle ord, der indeholder delordet 01. Den accepterer altså for eksempel ordet 101 eller 0101. Alle beregningens grene kan vi let visualisere ved hjælp af et træ, f.eks. kunne træet for ordet 01010 se sådan ud:

I begyndelsen er vi i starttilstanden q₀. Som input har vi ordet 01010, det første ulæste tegn er 0. Fra tilstanden q₀ går der to overgange for symbolet 0, til tilstandene q₀ og q₁. Træet får derfor i denne knude to børn: q₀ og q₁. Dernæst læser vi symbolet 1. Her er der ingen tvetydighed, vi flytter os til tilstandene q₀ og q₂. Dernæst læser vi tegnet 0, i den venstre gren opstår der igen tvetydighed, vi deler beregningen i to nye grene. I den ene bliver vi igen i q₀, og i den anden går vi til q₁. Og så videre.

Læg mærke til, at i alt to grene ender i tilstanden q₂, i en accepttilstand. Der findes to beregningsgrene, hvor automaten kan acceptere det givne ord. Denne automat ville altså acceptere ordet 01010. Vi kan prøve at lave et tilsvarende træ for ordet 1000.

Beregningen bliver enten i tilstanden q₀ eller går til tilstanden q₁, men derfra har den ingen steder at gå hen, for inputtet består nu kun af nuller, og tilstanden q₁ har kun en overgang for symbolet 1. Ingen beregningsgren ender i en accepttilstand, så automaten accepterer ikke ordet 1000.

Epsilon-overgange

I ikke-deterministiske automater kan vi desuden bruge epsilon-overgange. Det er overgange, som vi kan udføre, uanset hvilket symbol der er i input, og uden at vi læser noget symbol fra ordet. Hvordan kunne vi skrive en ikke-deterministisk automat, der accepterer det tomme ord, alle ord bestående kun af enere og ord af formen (10)ⁿ, dvs. 10, 1010, …?

Vi delte automaten i to »delautomater«. Den øverste sørger for at genkende ord, der består af 1, den nederste tager sig af ord af formen (10)ⁿ. Vi prøver at acceptere ordet 111. Automaten befinder sig i begyndelsen i tilstanden q₀ og har ordet 111 som input. Da den har epsilon-overgange til rådighed, kan den beslutte at gå til tilstanden q₁ eller q₂, alt efter hvad der passer den. Vi ser, at det passer den at gå til tilstanden q₁. Automaten går derhen. Og som input har den stadig ordet 111! Først nu begynder den at læse symboler fra ordet og gå fra tilstanden q₁ igen til q₁, indtil den har læst hele ordet og accepterer det.

Hvis vi prøvede at acceptere 1010, ville automaten i begyndelsen gå til tilstanden q₂ og først derfra begynde at behandle symbolerne og igen acceptere ordet.

For ordet 1100 kunne automaten gøre hvad som helst, den har ingen måde at acceptere et sådant ord på.

Epsilon-overgange og ikke-determinisme gør i mange henseender arbejdet lettere, for eksempel kan beviset for, at foreningen af regulære sprog igen er et regulært sprog, med epsilon-overgange skrives meget enklere end i tilfældet med deterministiske endelige automater. I dette bevis havde vi eksempler på disse automater

og

og videre konstruerede vi en endelig deterministisk automat, der accepterede foreningen af begge sprog. Med epsilon-overgange kan vi opstille en sådan automat sådan her:

Vi tilføjer simpelthen en ny starttilstand, fra den går to epsilon-overgange til de oprindelige starttilstande i de oprindelige automater, og det er det hele. Automaten beslutter sig ikke-deterministisk for, om den vil forsøge at acceptere ordet med den ene eller den anden »delautomat«.

Definition af en ikke-deterministisk automat

Vi har allerede vist, hvordan en deterministisk og en ikke-deterministisk endelig automat adskiller sig, nu mangler vi bare at formalisere det. En deterministisk endelig automat definerede vi som et femtupel ⟨Q, Σ, δ, q₀, F⟩, hvor Q er mængden af tilstande, Σ er alfabetet, δ er overgangsfunktionen, q₀ er starttilstanden og F er mængden af accepttilstande. Det eneste, der ændrer sig i definitionen af ikke-deterministiske automater, er definitionen af overgangsfunktionen.

I den deterministiske version kunne funktionen ved kaldet δ(q, w) kun returnere én tilstand, mens den i den ikke-deterministiske version kan returnere flere tilstande — hvis der for ét symbol er defineret flere overgange. Da vi også skal definere epsilon-overgange, betegner vi mængden Σ ∪ {ε} som mængden Σ_ε, dvs. Σ_ε = Σ ∪ {ε}. Funktionen δ definerer vi således som

$$\delta :Q\times {\mathrm{\Sigma }}_{\epsilon }\to 2^Q$$

2^Q betegner potensmængden, mængden af alle delmængder af mængden Q. Formaliseringen af beregningen ligner meget den for endelige automater. Automatens konfiguration er igen parret ⟨q, w⟩ ∈ Q × Σ^∗. Beregningstrinnet ↦ er en relation på mængden af konfigurationer, således at

$$⟨q_i,w_0{w}_1\dots w_n⟩\mapsto ⟨q_j,w_1\dots w_n⟩,$$

netop hvis q_j ∈ δ(q_i, w₀). Her ligger den største forskel. I deterministiske automater havde vi denne betingelse skrevet som q_j = δ(q_i, w₀), fordi funktionen δ altid returnerede én tilstand. Den ikke-deterministiske version af overgangsfunktionen returnerer en mængde af tilstande, derfor står symbolet ∈ der. Den refleksive og transitive afslutning af relationen betegner vi igen ↦ ^∗. Vi siger, at automaten accepterer ordet w netop hvis der findes q_f ∈ F, således at

$$⟨q_0,w⟩{\mapsto }^{\ast }⟨q_f,\epsilon ⟩.$$

Kilder

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools