Ändlig automat

En ändlig automat (på engelska finite state machine eller finite automaton) är en beräkningsmodell för en primitiv dator. Den består av några tillstånd och några övergångar och kan acceptera eller förkasta ett ord som den får.

Exempel

Informellt beskriver vi en ändlig automat med hjälp av ett tillståndsdiagram:

Automaten består av tillstånd, och i figuren är det tre runda tillstånd q₀, q₁ och q₂. Mellan tillstånden finns övergångar, det är pilarna. I automaten måste det dessutom finnas ett starttillstånd, och det är tillståndet q₀. Starttillståndet visas ofta så att en pil som inte utgår från något tillstånd pekar in i det. Vidare finns i en automat vanligtvis ett sluttillstånd, som vi ritar med en dubbel linje, så i figuren är det tillståndet q₂.

En sådan automat accepterar vissa ord. Vi matar alltså in några ord i automaten, och automaten försöker acceptera dem. Om den accepterar ordet svarar automaten JA, och om den inte gör det svarar den NEJ. Vår automat försöker acceptera ord som består av bokstäverna ”a, b, c”, så vi kan prova att acceptera ordet ”abbc”.

Vi börjar i starttillståndet q₀, och indata är ordet ”abbc”. Därefter följer vi pilarna.

Vi går igenom ordet på vanligt sätt från vänster till höger, så den första symbolen vi tar är ”a”. Pilen för indata ”a” går till tillståndet q₁, så vi går dit och tar bort symbolen ”a” från ordet. Som indata har vi ordet ”bbc”:

Pilen för indata ”b” går tillbaka till noden q₁. Vi tar åter bort den första bokstaven, och som indata har vi ordet ”bc”. Vi blir kvar i tillståndet q₁. Till slut har vi ordet ”c” som indata. Från tillståndet q₁ skickar pilen för indata ”c” oss till tillståndet q₂.

Vi har nu förbrukat alla bokstäver i indataordet och befinner oss i tillståndet q₂, som är ett sluttillstånd. Den här ändliga automaten accepterar alltså ordet ”abbc”.

Om vi inte hade befunnit oss i ett accepterande tillstånd i slutet, skulle automaten inte ha accepterat ordet. På samma sätt skulle automaten inte acceptera ordet om vi i något tillstånd inte hade någonstans att gå. För indata ”ab” skulle vi till exempel hamna i tillståndet q₁ och stanna där — automaten accepterar inte ett sådant ord. Om vi testar ordet ”aabbc” har vi återigen otur, eftersom det från tillståndet q₁ inte går någon pil för bokstaven ”a”.

En ändlig automat används alltså för att känna igen någon mängd av ord. I praktiken skulle vi kunna använda en automat till exempel för att avgöra om ett givet indataord är en giltig e-postadress.

Definition av ändlig automat

Den föregående intuitiva bilden av vad en ändlig automat är måste vi formalisera, så att vi kan arbeta vidare med automater på ett bättre sätt.

Vi säger att en ändlig (deterministisk) automat är en femtipel (Q, Σ, δ, q₀, F), där

• Q är en ändlig mängd av tillstånd,
• Σ (stort sigma) är ett alfabet (en ändlig mängd av symboler/bokstäver),
• δ: Q × Σ ⟶ Q är övergångsfunktionen,
• q₀ ∈ Q är starttillståndet,
• F ⊆ Q är mängden av sluttillstånd (accepterande tillstånd).

Om vi går tillbaka till den föregående automaten,

kan vi säga att det i tillståndsmängden Q finns tre tillstånd, Q = {q₀, q₁, q₂}. Alfabetet Σ innehåller de bokstäver som vi kan bilda ord av, och som automaten sedan accepterar eller förkastar. Här är det sannolikt alfabetet Σ= {a, b, c}, men det kan också vara en godtycklig övermängd. Starttillståndet q₀ är tillståndet q₀, där ändras ingenting. Mängden av sluttillstånd har i den här automaten bara ett tillstånd, F = {q₂}.

Med övergångsfunktionen menar vi de tre pilarna med bokstäver. Om beteckningen δ: Q × Σ ⟶ Q förvirrar dig, betyder den bara att δ är en funktion (eller snarare en avbildning) som tar två parametrar: ett tillstånd ur Q och en bokstav ur Σ. När vi anropar funktionen returnerar den ett nytt tillstånd. Vår övergångsfunktion kan vi definiera med en tabell så här:

$$\begin{array}{ccc}Q& \mathrm{\Sigma }& \to Q\\ q_0& a& q_1\\ q_1& b& q_1\\ q_1& c& q_2\end{array}$$

Om vi anropar δ(q₁, c) tillämpar vi den tredje raden, och funktionen svarar med tillståndet q₂ — precis som diagrammet. Om vi är i tillståndet q₁ och indata är bokstaven ”c”, hamnar vi i tillståndet q₂. Innan vi formellt definierar vad det betyder att en automat accepterar ett ord, använder vi den intuitiva förståelsen av begreppet och visar några fler exempel.

Fler exempel

1. Konstruera en automat som arbetar över det binära alfabetet, dvs. Σ= {0, 1}, och som bara accepterar ord som slutar med en etta. Den accepterar till exempel orden 1, 01, 000001, 0101011.

   

   Vår automat har två tillstånd — starttillståndet q₀ och sluttillståndet q₁. Så fort vi har siffran 1 som indata går vi till sluttillståndet q₁ och blir kvar där. Om indata däremot är siffran 0, går vi till det icke-accepterande tillståndet q₀ och blir också kvar där.

2. Konstruera en automat över det binära alfabetet som bara accepterar ord vars första bokstav skiljer sig från den sista bokstaven.

   

   Automaten delar sig redan i första steget i två ”delautomater”. Om ordet börjar med noll går automaten in i den vänstra delen och blir kvar där, och om det börjar med en etta går den till den högra delen. Sedan är det enkelt: om vi är i den vänstra delen och indata är 1, går vi till ett sluttillstånd och blir kvar där. Om indata är 0, går vi till tillståndet q₁, som inte är ett sluttillstånd.

   Till skillnad från de föregående automaterna har den här automaten flera sluttillstånd, dvs. F = {q₃, q₄}.

3. Konstruera en automat över det binära alfabetet som bara accepterar ord som inte innehåller två nollor i rad.

   

   Den här automaten är intressant av två skäl: det första är att den accepterar det tomma ordet. Vi kan försöka mata in det tomma ordet i automaten, och automaten accepterar det om starttillståndet samtidigt är ett sluttillstånd, vilket är fallet för den här automaten. Eftersom det tomma ordet är ett ord som inte innehåller två nollor i rad, är det precis som det ska vara. Det andra intressanta är att alla tillstånd i den här automaten är sluttillstånd. Det enda fallet då automaten inte accepterar ett ord är när det inte går någon övergång från ett tillstånd. Det händer i tillståndet q₁, som inte har någon övergång för 0, eftersom ordet då skulle innehålla två nollor i rad.

4. Konstruera en automat över alfabetet {-,+,.,0,1,…,9} som bara accepterar ord som representerar ett tal. Det betyder antingen ett heltal som till exempel 2, 548, 98263, eller ett decimaltal som till exempel 5584.48, 3.14, och båda i en version för negativa tal med minustecken -2, -548, -3.14 och även med ett uttryckligt plustecken, dvs. +2, +548, +3.14. Samtidigt måste vi kunna skriva talet 0.123 bara som .123 (utan nollan i början), och det med båda tecknen. Vi inför en hjälpbeteckning där vi, i stället för att skriva ut tio övergångar för tio siffror, använder symbolen N.

   

5. Konstruera en automat över det binära alfabetet som bara accepterar ord av formen 0ⁿ1ⁿ, vilket betyder att orden har ett visst antal nollor i början och därefter lika många ettor. Exempel på sådana ord är 0011, 00001111, 01.

   En sådan automat går inte att konstruera, eftersom vi inte kan ”komma ihåg” antalet nollor någonstans. Vi skulle behöva skapa flera ”delautomater”, ungefär som i det andra exemplet, men det skulle behövas oändligt många ”delautomater”, en för varje värde på n.

Formalisering av automatens beräkning

Vi har nu formellt definierat själva ändliga automaten. Därefter måste vi definiera vad en sådan automat egentligen gör, dvs. vi definierar automatens beräkning.

Automatens konfiguration: vi säger att paret (q, w) ∈ Q × Σ^∗ är en konfiguration av automaten, där q är det aktuella tillståndet som automaten befinner sig i och w är den hittills olästa delen av ordet. Σ^∗ betecknar Kleenestjärnan av alfabetet Σ, mängden av alla ord som kan bildas av bokstäverna i alfabetet Σ. Till Kleenestjärnan hör även det tomma ordet, som vi betecknar ε.

Om vi har automaten (Q, Σ, δ, q₀, F) och försöker acceptera ordet w, befinner sig automaten i startkonfigurationen (q₀, w). Om vi går tillbaka till automaten

och vill acceptera ordet w = abbc, blir startkonfigurationen (q₀, abbc).

Beräkningssteget definierar vi som en relation ↦ mellan mängderna (Q × Σ^∗) × (Q × Σ^∗), dvs. mellan automatens konfigurationer. Låt w = w₀w₁… w_n vara den hittills olästa delen av ordet w. Då säger vi att paren (q₁, w₀w₁… w_n) och (q₂, w₁… w_n) står i relationen ↦, vilket vi skriver som

$$(q_1,w_0{w}_1\dots w_n)\mapsto (q_2,w_1\dots w_n),$$

om och endast om δ(q₁, w₀) = q₂. Om vi går tillbaka till vårt exempel är startkonfigurationen (q₀, abbc). Av diagrammet ser vi att vi för indata ”a” kan flytta till tillståndet q₁. Vi kan alltså skriva

$$(q_0,abbc)\mapsto (q_1,bbc),$$

eftersom δ(q₀, a) = q₁ gäller. Därmed har vi genomfört ett beräkningssteg — vi tittade på vilket tillstånd vi ska gå till för den givna indata (= den första bokstaven i den hittills olästa delen av ordet), gick dit och tog bort den första bokstaven ur den olästa delen av ordet. På så sätt fick vi en ny konfiguration.

Det reflexiva och transitiva höljet av relationen beräkningssteg betecknar vi ↦ ^∗. Om vi skriver K₁ ↦ ^∗ K₂, där K₁, K₂ är konfigurationer av automaten, betyder det att vi från konfigurationen K₁ kan ta oss till konfigurationen K₂ genom flera beräkningssteg, eller med andra ord att det finns en ändlig följd av konfigurationer sådan att:

$$K_1\mapsto K_{11}\mapsto K_{12}\mapsto K_{13}\mapsto \cdots \mapsto K_2$$

I vår automat gäller till exempel (q₀, abbc) ↦ ^∗ (q₁, bc), eftersom vi efter två beräkningssteg har ordet ”bc” kvar och är kvar i tillståndet q₁. Det finns alltså den här följden av konfigurationer:

$$(q_0,abbc)\mapsto (q_1,bbc)\mapsto (q_1,bc)$$

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 )$$ Det betyder att automaten accepterar ordet w om och endast om det finns någon följd av beräkningssteg sådan att vi i slutet av följden har läst hela ordet och befinner oss i ett av automatens sluttillstånd. Att vi har läst hela ordet uttrycks av att ε, det tomma ordet, står på ordets plats i konfigurationen. Vår automat accepterar ordet abbc, eftersom det finns den här följden av konfigurationer:

$$(q_0,abbc)\mapsto (q_1,bbc)\mapsto (q_1,bc)\mapsto (q_1,c)\mapsto (q_2,\epsilon )$$

och tillståndet q₂ är ett sluttillstånd, q₂ ∈ F.

Språket som automaten accepterar är mängden av alla ord som automaten accepterar. Språket som automaten A accepterar betecknar vi L(A). Det gäller alltså att L(A) ⊆ Σ^∗ och

$$L(A)=\{w\in {\mathrm{\Sigma }}^{\ast }\mid A\text{ accepterar ordet }w\}$$

Ett reguljärt språk är ett språk som accepteras av någon ändlig automat.

Två ändliga automater är ekvivalenta om de accepterar samma språk. Dvs. automaterna A₁ och A₂ är ekvivalenta om L(A₁) = L(A₂).

Källor

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