Endelig automat

En endelig automat (på engelsk finite state machine eller finite automaton) er en beregningsmodell for en primitiv datamaskin. Den består av noen tilstander og noen overganger, og den kan akseptere eller avvise et ord den får oppgitt.

Eksempel

Uformelt beskriver vi en endelig automat ved hjelp av et tilstandsdiagram:

Automaten er bygd opp av tilstander. På figuren er det tre runde tilstander q₀, q₁ og q₂. Mellom tilstandene går det overganger, det er pilene. I automaten må det dessuten finnes en starttilstand, og det er tilstanden q₀. Starttilstanden tegnes ofte slik at en pil som ikke kommer fra noen tilstand, peker på den. Videre har automaten vanligvis en sluttilstand, som vi tegner med dobbel strek, så på figuren er det tilstanden q₂.

En slik automat aksepterer visse ord. Vi sender ord inn i automaten, og automaten prøver å akseptere dem. Hvis den aksepterer ordet, svarer den JA, og hvis den ikke gjør det, svarer den NEI. Automaten vår prøver å akseptere ord som består av bokstavene «a, b, c», så vi kan prøve ordet «abbc».

Vi begynner i starttilstanden q₀, og input er ordet «abbc». Videre følger vi pilene.

Vi går gjennom ordet på vanlig måte fra venstre til høyre, så det første symbolet vi tar, er «a». Pilen for input «a» går til tilstanden q₁, så dit går vi over, og vi fjerner symbolet «a» fra ordet. Som input har vi nå ordet «bbc»:

Pilen for input «b» peker tilbake til noden q₁. Vi fjerner igjen den første bokstaven, og som input har vi ordet «bc». Vi blir igjen i tilstanden q₁. Til slutt har vi ordet «c» som input. Fra tilstanden q₁ sender pilen for input «c» oss til tilstanden q₂.

Nå har vi brukt opp alle bokstavene i inputordet, og vi er i tilstanden q₂, som er en sluttilstand. Denne endelige automaten aksepterer altså ordet «abbc».

Hvis vi ikke hadde vært i en aksepterende tilstand til slutt, ville automaten ikke ha akseptert ordet. På samme måte ville automaten ikke ha akseptert ordet hvis vi i en tilstand ikke hadde noe sted å gå. For input «ab» ville vi for eksempel ha kommet til tilstanden q₁ og blitt stående der — automaten aksepterer ikke et slikt ord. Hvis vi prøver ordet «aabbc», har vi igjen uflaks, for fra tilstanden q₁ går det ingen pil for bokstaven «a».

En endelig automat brukes altså til å gjenkjenne en mengde ord. I praksis kunne vi brukt en automat til å finne ut om et gitt inputord er en gyldig e-postadresse.

Definisjon av endelig automat

Den forrige intuitive forestillingen om hva en endelig automat er, må vi formalisere for at vi skal kunne arbeide videre og bedre med automater.

Vi sier at en endelig (deterministisk) automat er et femtuppel ⟨Q, Σ, δ, q₀, F⟩, der

• Q er en endelig mengde av tilstander,
• Σ (stor sigma) er alfabetet (en endelig mengde av symboler/bokstaver),
• δ: Q × Σ ⟶ Q er overgangsfunksjonen,
• q₀ ∈ Q er starttilstanden,
• F ⊆ Q er mengden av sluttilstander (aksepterende tilstander).

Hvis vi går tilbake til den forrige automaten,

kan vi si at mengden av tilstander Q inneholder tre tilstander, Q = {q₀, q₁, q₂}. Alfabetet Σ inneholder bokstavene vi kan sette sammen til ord som automaten så skal akseptere eller avvise. Her er det sannsynligvis alfabetet Σ= {a, b, c}, men det kan også være en vilkårlig supermengde. Starttilstanden q₀ er tilstanden q₀, her er det ingenting å legge til. Mengden av sluttilstander har i denne automaten bare én tilstand, F = {q₂}.

Med overgangsfunksjonen mener vi de tre pilene med bokstaver. Hvis du blir forvirret av skrivemåten δ: Q × Σ ⟶ Q, betyr den bare at δ er en funksjon (kanskje bedre: en avbildning) som tar to parametere: en tilstand fra Q og en bokstav fra Σ. Når vi kaller funksjonen, returnerer den en ny tilstand. Overgangsfunksjonen vår kunne vi definert med en tabell slik:

$$\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 kaller δ(q₁, c), bruker vi tredje rad, og funksjonen svarer med tilstanden q₂ — akkurat som diagrammet. Hvis vi er i tilstanden q₁ og bokstaven «c» står som input, kommer vi til tilstanden q₂. Før vi definerer formelt hva det betyr at en automat aksepterer et ord, bruker vi den intuitive forståelsen av begrepet og viser noen flere eksempler.

Flere eksempler

1. Lag en automat som arbeider over det binære alfabetet, altså Σ= {0, 1}, og som bare aksepterer ord som slutter på en ener. Den aksepterer for eksempel ordene 1, 01, 000001, 0101011.

   

   Automaten vår har to tilstander — starttilstanden q₀ og sluttilstanden q₁. Så snart vi har sifferet 1 som input, går vi over til sluttilstanden q₁ og blir værende der. Hvis derimot sifferet 0 er input, går vi over til tilstanden q₀, som ikke er en sluttilstand, og blir også værende der.

2. Lag en automat over det binære alfabetet som bare aksepterer ord der den første bokstaven er forskjellig fra den siste bokstaven.

   

   Allerede i det første steget deler automaten seg i to «delautomater». Hvis ordet begynner med null, går automaten inn i den venstre delen og blir værende der, og hvis det begynner med en ener, flytter den seg til den høyre delen. Etter det er det helt vanlig: hvis vi er i den venstre delen og input er 1, flytter vi oss til sluttilstanden og blir værende der. Hvis input er 0, flytter vi oss til tilstanden q₁, som ikke er en sluttilstand.

   I motsetning til de forrige automatene har denne automaten flere sluttilstander, altså F = {q₃, q₄}.

3. Lag en automat over det binære alfabetet som bare aksepterer ord som ikke inneholder to nuller etter hverandre.

   

   Denne automaten er interessant av to grunner. Den første er at den aksepterer det tomme ordet. Vi kan prøve å sende det tomme ordet inn i automaten, og automaten aksepterer det hvis starttilstanden samtidig er en sluttilstand, og det er tilfellet for denne automaten. Siden det tomme ordet er et ord som ikke inneholder to nuller etter hverandre, er dette riktig. Den andre interessante tingen er at alle tilstandene i denne automaten er sluttilstander. Det eneste tilfellet der automaten ikke aksepterer et ord, er når det ikke går noen overgang ut av tilstanden. Det skjer i tilstanden q₁, som ikke har noen overgang for 0, for da ville ordet inneholdt to nuller etter hverandre.

4. Lag en automat over alfabetet {-,+,.,0,1,…,9} som bare aksepterer ord som representerer et tall. Det betyr enten et heltall, for eksempel 2, 548, 98263, eller et desimaltall, for eksempel 5584.48, 3.14 (her skrevet med punktum som desimaltegn, slik det gjøres i programmering), og begge deler også i en versjon for negative tall med minustegn -2, -548, -3.14 og med eksplisitt skrevet pluss, altså +2, +548, +3.14. Samtidig må vi kunne skrive tallet 0.123 bare som .123 (uten nullen først), også med begge fortegnene. Vi innfører en hjelpebetegnelse: i stedet for å skrive ti overganger for ti sifre bruker vi symbolet N.

   

5. Lag en automat over det binære alfabetet som bare aksepterer ord på formen 0ⁿ1ⁿ, som betyr at ordene har et visst antall nuller først, etterfulgt av like mange enere. Eksempler på slike ord er 0011, 00001111, 01.

   En slik automat kan ikke bygges, fordi vi ikke har noe sted der vi kan «huske» antallet nuller. Vi måtte laget flere «delautomater», på samme måte som i det andre eksempelet, men det måtte vært uendelig mange «delautomater», én for hver verdi av n.

Formalisering av automatens beregning

Vi har nå definert selve den endelige automaten formelt. Videre må vi definere hva en slik automat egentlig gjør, altså vi definerer automatens beregning.

Automatens konfigurasjon: Vi sier at paret ⟨q, w⟩ ∈ Q × Σ^∗ er en konfigurasjon av automaten, der q er tilstanden automaten befinner seg i nå, og w er den delen av ordet som ennå ikke er lest. Σ^∗ betegner Kleene-stjernen av alfabetet Σ, mengden av alle ord som kan settes sammen av bokstavene i alfabetet Σ. Det tomme ordet, som vi betegner ε, er også med i Kleene-stjernen.

Hvis vi har automaten ⟨Q, Σ, δ, q₀, F⟩ og prøver å akseptere ordet w, befinner automaten seg i startkonfigurasjonen ⟨q₀, w⟩. Hvis vi går tilbake til automaten

og vil akseptere ordet w = abbc, blir startkonfigurasjonen ⟨q₀, abbc⟩.

Beregningssteg definerer vi som en relasjon ↦ mellom mengdene (Q × Σ^∗) × (Q × Σ^∗), altså mellom konfigurasjoner av automaten. La w = w₀w₁… w_n være den delen av ordet w som ennå ikke er lest. Da sier vi at parene ⟨q₁, w₀w₁… w_n⟩ og ⟨q₂, w₁… w_n⟩ står i relasjonen ↦, og vi skriver

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

hvis og bare hvis δ(q₁, w₀) = q₂. I eksempelet vårt er startkonfigurasjonen ⟨q₀, abbc⟩. Fra diagrammet ser vi at vi for input «a» kan flytte oss til tilstanden q₁. Vi kan derfor skrive

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

fordi δ(q₀, a) = q₁. Dermed har vi utført ett beregningssteg — vi har sett hvilken tilstand vi skal gå til for det gitte inputet (= den første bokstaven i den ikke leste delen av ordet), vi har gått dit, og vi har fjernet den første bokstaven fra den ikke leste delen av ordet. Slik har vi fått en ny konfigurasjon.

Den refleksive og transitive tillukningen av relasjonen beregningssteg betegner vi ↦ ^∗. Hvis vi skriver K₁ ↦ ^∗ K₂, der K₁, K₂ er konfigurasjoner av automaten, betyr det at vi fra konfigurasjonen K₁ kan komme til konfigurasjonen K₂ gjennom flere beregningssteg, eller med andre ord at det finnes en endelig følge av konfigurasjoner slik at:

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

I automaten vår gjelder for eksempel ⟨q₀, abbc⟩ ↦ ^∗ ⟨q₁,bc⟩, for når vi utfører to beregningssteg, blir ordet «bc» igjen, og vi blir i tilstanden q₁. Altså finnes denne følgen av konfigurasjoner:

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

Automaten aksepterer ordet w hvis og bare hvis det finnes en q_f ∈ F slik at $$⟨q_0,w⟩{\mapsto }^{\ast }⟨q_f,\epsilon ⟩$$ Det betyr at automaten aksepterer ordet w hvis og bare hvis det finnes en følge av beregningssteg slik at vi på slutten av følgen har lest hele ordet og befinner oss i en sluttilstand i automaten. At vi har lest hele ordet, uttrykkes ved at det i konfigurasjonen står ε, det tomme ordet, der ordet skulle stått. Automaten vår aksepterer ordet abbc, fordi det finnes denne følgen av konfigurasjoner:

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

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

Språket som automaten aksepterer, er mengden av alle ord som automaten aksepterer. Språket til automaten A betegner vi L(A). Da gjelder L(A) ⊆ Σ^∗ og

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

Et regulært språk er et språk som aksepteres av en endelig automat.

To endelige automater er ekvivalente hvis de aksepterer det samme språket. Altså er automatene A₁ og A₂ ekvivalente hvis L(A₁) = L(A₂).

Kilder

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