Endelig automat

En endelig automat (på engelsk finite state machine eller finite automaton) er en beregningsmodel for en primitiv computer, som består af nogle tilstande og nogle overgange, og som kan acceptere eller afvise et ord, den får givet.

Eksempel

Uformelt beskriver vi en endelig automat ved hjælp af et tilstandsdiagram, som beskriver den endelige automat:

Automaten består af tilstande, på figuren er det tre runde tilstande q₀, q₁ og q₂. Mellem disse tilstande er der overgange, det er pilene. I automaten skal der desuden være en starttilstand, det er tilstanden q₀. Starttilstanden tegner man ofte, så der peger en pil ind i den, som ikke udgår fra nogen tilstand. Desuden har automaten typisk en accepttilstand, den tegner vi med en dobbelt streg, så på figuren er det tilstanden q₂.

En automat opbygget på denne måde accepterer nogle ord. Vi giver automaten nogle ord, og automaten forsøger at acceptere dem. Hvis den accepterer dem, svarer automaten JA, hvis ikke, svarer den NEJ. Vores automat forsøger at acceptere ord, der består af bogstaverne »a, b, c«, så vi kan prøve at acceptere ordet »abbc«.

Vi begynder i starttilstanden q₀, og inputtet er ordet »abbc«. Derefter følger vi pilene.

Ordet gennemgår vi som sædvanlig fra venstre mod højre, det vil sige, at vi først tager symbolet »a«. Pilen for input »a« går til tilstanden q₁, så vi går derhen og fjerner symbolet »a« fra ordet. Som input har vi ordet »bbc«:

Pilen for input »b« peger tilbage til knuden q₁. Igen fjerner vi det første bogstav, og som input har vi ordet »bc«. Igen bliver vi i tilstanden q₁. Til sidst har vi som input ordet »c«. Fra tilstanden q₁ sender pilen for input »c« os til tilstanden q₂.

Nu har vi brugt alle bogstaverne i inputordet, og vi er i tilstanden q₂, som er en accepttilstand. Denne endelige automat accepterer altså ordet »abbc«.

Hvis vi ikke var i en accepttilstand til sidst, ville automaten ikke acceptere ordet. På samme måde ville automaten ikke acceptere ordet, hvis vi i en tilstand ikke havde noget sted at gå hen. For inputtet »ab« ville vi for eksempel nå til tilstanden q₁ og ende der — automaten accepterer ikke et sådant ord. Hvis vi testede ordet »aabbc«, ville vi igen være uheldige, for fra tilstanden q₁ går der ingen pil for bogstavet »a«.

En endelig automat tjener altså til at genkende en mængde af ord. I praksis kunne vi bruge automaten til for eksempel at afgøre, om et givet inputord er en gyldig e-mail.

Definition af en endelig automat

Den foregående intuitive forestilling om, hvad en endelig automat er, må vi formalisere, for at vi kan arbejde videre og bedre med automater.

Vi siger, at en endelig (deterministisk) automat er et femtupel ⟨Q, Σ, δ, q₀, F⟩, hvor

• Q er en endelig mængde af tilstande,
• Σ (stort sigma) er alfabetet (en endelig mængde af symboler/bogstaver),
• δ: Q × Σ ⟶ Q er overgangsfunktionen,
• q₀ ∈ Q er starttilstanden,
• F ⊆ Q er mængden af accepttilstande.

Hvis vi vender tilbage til den foregående automat,

kan vi sige, at der i mængden af tilstande Q er tre tilstande Q = {q₀, q₁, q₂}. Alfabetet Σ indeholder de bogstaver, som vi kan sætte ord sammen af, og som automaten så vil acceptere eller afvise. Her er det formentlig alfabetet Σ= {a, b, c}, men det kan også være en vilkårlig overmængde. Starttilstanden q₀ er tilstanden q₀, det ændrer sig ikke. Mængden af accepttilstande har i denne automat kun én tilstand F = {q₂}.

Ved overgangsfunktionen forstår vi så de tre pile med bogstaver. Hvis notationen δ: Q × Σ ⟶ Q forvirrer dig, betyder den bare, at δ er en funktion (måske bedre en afbildning), som tager to parametre: en tilstand fra Q og et bogstav fra Σ. Når funktionen kaldes, returnerer den en ny tilstand. Vores overgangsfunktion kunne vi definere med en tabel sådan:

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

Hvis vi kalder δ(q₁, c), anvender vi den tredje række, og funktionen svarer med tilstanden q₂ — ligesom diagrammet. Hvis vi er i tilstanden q₁, og inputtet er bogstavet »c«, havner vi i tilstanden q₂. Før vi formelt definerer, hvad det vil sige, at en automat accepterer et ord, bruger vi den intuitive forståelse af dette begreb og ser nogle flere eksempler.

Flere eksempler

1. Lav en automat, der arbejder over det binære alfabet, dvs. Σ= {0, 1}, og kun accepterer ord, der ender på et ettal. Den accepterer f.eks. ordene 1, 01, 000001, 0101011.

   

   Vores automat har to tilstande — starttilstanden q₀ og accepttilstanden q₁. Hver gang inputtet er cifferet 1, går vi til accepttilstanden q₁ og bliver i den. Er inputtet derimod cifferet 0, går vi til den ikke-accepterende tilstand q₀ og bliver også i den.

2. Konstruér en automat over det binære alfabet, der kun accepterer ord, hvis første bogstav er forskelligt fra det sidste bogstav.

   

   Automaten deler sig allerede i det første skridt i to »delautomater«. Hvis ordet begynder med nul, går automaten ind i den venstre del og bliver der, hvis det begynder med et, flytter den sig til den højre del. Derefter er det klassisk: hvis vi er i den venstre del, og inputtet er 1, flytter vi os til accepttilstanden og bliver der. Hvis inputtet er 0, flytter vi os til tilstanden q₁, som ikke er accepterende.

   I modsætning til de foregående automater har denne automat flere accepttilstande, dvs. F = {q₃, q₄}.

3. Konstruér en automat over det binære alfabet, der kun accepterer ord, som ikke indeholder to nuller i træk.

   

   Denne automat er interessant af to grunde: den første er, at den accepterer det tomme ord. Vi kan prøve at give automaten det tomme ord, og automaten accepterer det, hvis starttilstanden samtidig er en accepttilstand, hvilket er tilfældet for denne automat. Da det tomme ord er et ord, der ikke indeholder to nuller i træk, er det den rigtige opførsel. Den anden mærkværdighed er, at alle tilstande i denne automat er accepterende. Det eneste tilfælde, hvor automaten ikke ville acceptere ordet, er, når der fra en tilstand ikke går nogen overgang. Det sker i tilstanden q₁, som ikke har nogen overgang for 0, for så ville ordet indeholde to nuller i træk.

4. Konstruér en automat over alfabetet {-,+,.,0,1,…,9}, der kun accepterer ord, som repræsenterer et tal. Det betyder enten et helt tal som f.eks. 2, 548, 98263, eller et decimaltal som f.eks. 5584.48, 3.14 og begge dele også med en version for negative tal med minustegn -2, -548, -3.14 og også med eksplicit angivet plus, dvs. +2, +548, +3.14. Samtidig skal vi kunne skrive tallet 0.123 bare som .123 (uden nullet i begyndelsen), og det med begge fortegn. Vi indfører en hjælpenotation, hvor vi i stedet for at skrive ti overgange for ti cifre bruger symbolet N.

   

5. Konstruér en automat over det binære alfabet, der kun accepterer ord af formen 0ⁿ1ⁿ, hvilket betyder, at ordene har et vist antal nuller i begyndelsen efterfulgt af lige så mange enere. Eksempler på sådanne ord er 0011, 00001111, 01.

   En sådan automat kan ikke konstrueres, fordi vi ingen steder kan »huske« antallet af nuller. Vi ville skulle lave flere »delautomater«, ligesom i det andet eksempel, men der skulle være uendeligt mange »delautomater«, én for hver værdi af n.

Formalisering af automatens beregning

Vi har allerede formelt defineret selve den endelige automat. Nu mangler vi at definere, hvad en sådan automat egentlig gør, dvs. vi definerer automatens beregning.

Automatens konfiguration: Vi siger, at parret ⟨q, w⟩ ∈ Q × Σ^∗ er en konfiguration af automaten, hvor q er den aktuelle tilstand, som automaten befinder sig i, og w er den hidtil ulæste del af ordet. Σ^∗ betegner afslutningen af alfabetet Σ, altså mængden af alle ord, der kan sættes sammen af bogstaverne i alfabetet Σ. Afslutningen indeholder også det tomme ord, som vi betegner ε.

Hvis vi har automaten ⟨Q, Σ, δ, q₀, F⟩ og forsøger at acceptere ordet w, befinder automaten sig i startkonfigurationen ⟨q₀, w⟩. Hvis vi vender tilbage til automaten

og vil acceptere ordet w = abbc, er startkonfigurationen ⟨q₀, abbc⟩.

Beregningstrin definerer vi som en relation ↦ mellem mængderne (Q × Σ^∗) × (Q × Σ^∗), dvs. mellem automatens konfigurationer. Lad w = w₀w₁… w_n være den hidtil ulæste del af ordet w. Så siger vi, at parrene ⟨q₁, w₀w₁… w_n⟩ og ⟨q₂, w₁… w_n⟩ står i relationen ↦, hvilket vi skriver som

$$⟨q_1,w_0{w}_1\dots w_n⟩\mapsto ⟨q_2,w_1\dots w_n⟩,$$

netop hvis δ(q₁, w₀) = q₂. Hvis vi vender tilbage til vores eksempel, er startkonfigurationen ⟨q₀, abbc⟩. Af diagrammet ser vi, at vi for input »a« kan flytte os til tilstanden q₁. Vi kan derfor skrive

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩,$$

fordi δ(q₀, a) = q₁. Dermed har vi udført ét beregningstrin — vi har set, hvilken tilstand vi skal gå til for det givne input (= det første bogstav i den hidtil ulæste del af ordet), vi er gået derhen og har fjernet det første bogstav fra den ulæste del af ordet. Dermed har vi fået en ny konfiguration.

Den refleksive og transitive afslutning af relationen beregningstrin betegner vi ↦ ^∗. Hvis vi skriver K₁ ↦ ^∗ K₂, hvor K₁, K₂ er konfigurationer af automaten, betyder det, at vi fra konfigurationen K₁ kan nå til konfigurationen K₂ gennem nogle beregningstrin, eller med andre ord, at der findes en endelig følge af konfigurationer, således at:

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

I vores automat gælder for eksempel ⟨q₀, abbc⟩ ↦ ^∗ ⟨q₁,bc⟩, fordi når vi udfører to beregningstrin, er ordet »bc« tilbage, og vi er i tilstanden q₁. Dvs. der findes denne følge af konfigurationer:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩$$

Automaten accepterer ordet w netop hvis der findes q_f ∈ F, således at $$⟨q_0,w⟩{\mapsto }^{\ast }⟨q_f,\epsilon ⟩$$ Det betyder, at automaten accepterer ordet w netop hvis der findes en følge af beregningstrin, således at vi i slutningen af denne følge har læst hele ordet og befinder os i en accepttilstand i automaten. At vi har læst hele ordet, udtrykkes ved, at der i konfigurationen står ε på ordets plads, altså det tomme ord. Vores automat accepterer ordet abbc, fordi der findes denne følge af konfigurationer:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩\mapsto ⟨q_1,c⟩\mapsto ⟨q_2,\epsilon ⟩$$

og tilstanden q₂ er en accepttilstand, q₂ ∈ F.

Det sprog, som automaten accepterer, er mængden af alle ord, som automaten accepterer. Sproget for automaten A betegner vi L(A). Der gælder således, at L(A) ⊆ Σ^∗ og

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

Et regulært sprog er et sprog, som accepteres af en endelig automat.

To endelige automater er ækvivalente, hvis de accepterer samme sprog. Dvs. automaterne A₁ og A₂ er ækvivalente, hvis L(A₁) = L(A₂).

Kilder

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