Icke-deterministisk ändlig automat

Den ändliga automat som vi presenterade i de tidigare kapitlen (förkortas DFA) var alltid deterministisk, vilket visade sig i att det i varje ögonblick var klart vad automaten gör. Nu tittar vi på det mer allmänna begreppet icke-deterministiska ändliga automater (förkortas NFA), där det kan finnas övergångar som utgår från samma tillstånd och gäller för samma symbol.

Exempel

Titta på följande automatdiagram:

Vad är speciellt med det? Att det från noden q₀ går två bågar för symbolen 0. Om vi försöker acceptera ordet 001 verkar det alltså som om automaten inte skulle veta om den ska stanna kvar i tillståndet q₀ eller följa övergången till q₁. En sådan automat vore icke-deterministisk.

Determinism betyder i det här sammanhanget att det i varje situation är klart vad automaten gör, att det inte finns utrymme för tvetydighet. En deterministisk automat har för varje tillstånd och varje symbol bara en övergång. Icke-determinism innebär tvetydighet — från ett tillstånd kan det för samma symbol gå till exempel tre övergångar.

Och hur bestämmer sig automaten då? En icke-deterministisk automat väljer alltid (ibland säger vi också att den ”gissar”) den övergång som leder till att ordet accepteras, om det är möjligt.

Om vi matar in ordet 001 i automaten har den de här möjligheterna att hantera 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 möjligheterna där den inte läser hela ordet. I den första blev den hela tiden kvar i tillståndet q₀, vilket den självklart kan, eftersom övergångsreglerna tillåter det. I den andra grenen vågade den sig vidare till andra tillstånd och kom till slut till tillståndet q₂, som är ett sluttillstånd. I den här grenen skulle automaten acceptera ordet. En icke-deterministisk automat väljer automatiskt den gren där den accepterar ordet, om en sådan gren finns.

Hur kan den automatiskt välja den ”gynnsamma” grenen? Vi kan tänka oss att den icke-deterministiska automaten går igenom alla möjliga grenar, och om den hittar en gren där den accepterar ordet, så accepterar den ordet. Hur skulle den kunna gå igenom alla grenar? Helt enkelt så att automaten, när den är i ett tillstånd som har n bågar för den aktuella symbolen, kopierar sig själv n gånger och varje kopia går en annan väg. På så sätt går vi successivt igenom alla möjligheter.

Trädrepresentation av automatens beräkning

Vi modifierar den föregående automaten något:

Icke-determinismen finns kvar i det första tillståndet. Den föregående automaten accepterade alla ord som slutar på 01. Den här modifierade automaten accepterar alla ord som innehåller delordet 01. Den accepterar alltså till exempel ordet 101 eller 0101. Alla beräkningsgrenar kan vi lätt visualisera med ett träd, och för ordet 01010 kan trädet till exempel se ut så här:

I början är vi i starttillståndet q₀. Som indata har vi ordet 01010, och det första olästa tecknet är 0. Från tillståndet q₀ går två övergångar för symbolen 0, till tillstånden q₀ och q₁. Trädet får alltså två barn i den här noden: q₀ och q₁. Sedan läser vi symbolen 1. Där finns ingen tvetydighet, vi går till tillstånden q₀ och q₂. Sedan läser vi tecknet 0, och i den vänstra grenen uppstår återigen tvetydighet, så vi delar beräkningen i två nya grenar. I den ena blir vi åter kvar i q₀ och i den andra går vi till q₁. Och så vidare.

Lägg märke till att totalt två grenar slutar i tillståndet q₂, i ett sluttillstånd. Det finns två beräkningsgrenar genom vilka automaten kan acceptera det givna ordet. Den här automaten skulle alltså acceptera ordet 01010. Vi kan försöka skapa ett motsvarande träd för ordet 1000.

Beräkningen blir antingen kvar i tillståndet q₀ eller går över till tillståndet q₁, men därifrån har den ingenstans att gå, eftersom indata nu bara består av nollor och tillståndet q₁ bara har en övergång för symbolen 1. Ingen beräkningsgren slutar i ett sluttillstånd, så automaten accepterar inte ordet 1000.

Epsilonövergångar

I icke-deterministiska automater kan vi dessutom använda epsilonövergångar. Det är övergångar som vi kan göra oavsett vilken symbol som är indata, och utan att vi läser någon symbol ur ordet. Hur skulle vi kunna skriva en icke-deterministisk automat som accepterar det tomma ordet, alla ord som bara består av ettor och ord av formen (10)ⁿ, dvs. 10, 1010, …?

Vi har delat upp automaten i två ”delautomater”. Den övre ser till att känna igen ord som består av ettor, den nedre tar hand om ord av formen (10)ⁿ. Vi försöker acceptera ordet 111. Automaten befinner sig i början i tillståndet q₀ och har ordet 111 som indata. Eftersom den har epsilonövergångar till sitt förfogande kan den bestämma sig för att gå till tillståndet q₁ eller q₂, beroende på vad som passar den. Vi ser att det passar den att gå till tillståndet q₁. Automaten går dit. Samtidigt har den fortfarande ordet 111 som indata! Först i det ögonblicket börjar den läsa symboler ur ordet och gå från tillståndet q₁ till q₁ igen, tills den har läst hela ordet och accepterar det.

Om vi försökte acceptera 1010, skulle automaten i början gå till tillståndet q₂ och först därifrån börja behandla symbolerna och återigen acceptera ordet.

För ordet 1100 kan automaten göra vad som helst, ett sådant ord har den inget sätt att acceptera.

Epsilonövergångar och icke-determinism underlättar vårt arbete på många sätt. Till exempel kan beviset för att unionen av reguljära språk åter är ett reguljärt språk skrivas mycket enklare med epsilonövergångar än i fallet med deterministiska ändliga automater. I det beviset hade vi exempel på de här automaterna

och

och vidare konstruerade vi en deterministisk ändlig automat som accepterade unionen av båda språken. Med epsilonövergångar kan vi bygga en sådan automat så här:

Vi lägger helt enkelt till ett nytt starttillstånd, från det går två epsilonövergångar till de ursprungliga starttillstånden i de ursprungliga automaterna, och det är allt. Automaten bestämmer sig icke-deterministiskt för om den ska försöka acceptera ordet med den ena eller den andra ”delautomaten”.

Definition av icke-deterministisk automat

Vi har redan visat hur en deterministisk och en icke-deterministisk ändlig automat skiljer sig åt, och det återstår bara att formalisera det. Den deterministiska ändliga automaten definierade vi som en femtipel (Q, Σ, δ, q₀, F), där Q är mängden av tillstånd, Σ är alfabetet, δ är övergångsfunktionen, q₀ är starttillståndet och F är mängden av sluttillstånd. Det enda som ändras i definitionen av icke-deterministiska automater är definitionen av övergångsfunktionen.

I den deterministiska versionen kunde funktionen vid anropet δ(q, w) returnera bara ett tillstånd, medan den i den icke-deterministiska versionen kan returnera flera tillstånd — om det för en symbol är definierat flera övergångar. Eftersom vi också behöver definiera epsilonövergångar betecknar vi mängden Σ ∪ {ε} som mängden Σ_ε, dvs. Σ_ε = Σ ∪ {ε}. Funktionen δ definierar vi alltså som

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

Beteckningen 2^Q står för potensmängden, mängden av alla delmängder av mängden Q. Formaliseringen av beräkningen är mycket lik den för ändliga automater. Automatens konfiguration är återigen paret (q, w) ∈ Q × Σ^∗. Beräkningssteget ↦ är en relation på mängden av konfigurationer sådan att

$$(q_i,w_0{w}_1\dots w_n)\mapsto (q_j,w_1\dots w_n),$$

om och endast om q_j ∈ δ(q_i, w₀). Det var i den här meningen som den största skillnaden fanns. I deterministiska automater hade vi det här villkoret skrivet som q_j = δ(q_i, w₀), eftersom funktionen δ alltid returnerade ett tillstånd. Den icke-deterministiska versionen av övergångsfunktionen returnerar en mängd av tillstånd, och därför står symbolen ∈ där. Det reflexiva och transitiva höljet av relationen betecknar vi återigen ↦ ^∗. Vi säger att automaten accepterar ordet w om och endast om det finns ett q_f ∈ F sådant att

$$(q_0,w){\mapsto }^{\ast }(q_f,\epsilon ).$$

Källor

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