Tillståndsmaskin

En tillståndsmaskin (eng State Machine eller Automaton) är en abstrakt modell som används till exempel inom mjukvaruutveckling, hårdvarudesign, beräkningsteori och språkvetenskap. Tillståndsmaskiner används för att beskriva skeenden i olika former med hjälp av tillstånd och villkor för övergång från ett tillstånd till ett annat.

Vanligen anses tillståndsmaskin vara synonymt med ändlig tillståndsmaskin (eng Finite State Machine eller Finite Automaton) då en tillståndsmaskin måste ha ett ändligt antal tillstånd för att vara praktiskt användbar.

Informell beskrivning

En tillståndsmaskin består av ett antal tillstånd och ett antal övergångar mellan dessa tillstånd. Ett exempel på en tillståndsmaskin kan vara en modell för en dörr:

Modell för Dörr:

Tillstånd : Öppen, Stängd

Övergångar: Öppna, Stäng

En tillståndsmaskin befinner sig alltid i ett tillstånd och om ett visst villkor uppfylls övergår tillståndsmaskinen till ett annat tillstånd. Om till exempel tillståndsmaskinen för Dörr befinner sig i tillståndet Stängd och villkoret för övergången Öppna inträffar (det vill säga, någon öppnar dörren) så övergår tillståndsmaskinens tillstånd till Öppen.

Tillståndsmaskiner beskrivs ofta med blocksymboler som representerar tillstånd och pilar som representerar övergångar. Villkoret för övergång skrivs vid pilen:

Tillståndsmaskin för Dörr

Låt oss anta att tillståndet Låst införs i modellen för dörr. Vilka nya övergångar kräver detta? Skall det till exempel finnas en övergång till Låst när dörren är i tillståndet Öppen. I en viss mening är det möjligt att låsa en öppen dörr, men funktionellt sett är det inte meningsfullt. Vi utökar dessutom tillståndsmaskinen med tillståndet Fel.

Utökad tillståndsmaskin för Dörr

Den valda tillståndsmaskinen kommer att stoppa i tillståndet Fel om man antingen försöker låsa eller låsa upp dörren när den är öppen, eller om man försöker öppna eller stänga dörren när den är låst. Det kanske finns ett bättre sätt att hantera felbeteenden på?

Robust tillståndsmaskin för Dörr

Bilden ovan visar en tillståndsmaskin för Dörr som inte stoppar på grund av fel. En tillståndsmaskin som hanterar felbeteenden eller felaktig input utan att stoppa sägs vara robust.

Modellen för Dörr ser nu ut så här:

Tillstånd: Öppen, Stängd, Låst

Övergångar: Öppna, Stäng, Lås, Lås upp

Formell beskrivning

En Finit Tillståndsmaskin (eng Finite State Machine (FSM) eller Finite Automaton) är ett mångsidigt och allmänt använt verktyg för att modellera förlopp med hjälp av tillstånd, övergångar och händelser.

• Ett tillstånd lagrar information om vad som har hänt under den tid som gått sedan det system som tillståndsmaskinen modellerar startades - det vill säga, den reflekterar de stimuli som systemet har utsatts för från att den startades fram till nuet.

• En övergång innebär en tillståndsändring och övergången beskrivs av en händelse som måste inträffa för att övergången ska äga rum.

• En händelse är en beskrivning av en aktivitet som inträffar i ett givet ögonblick.

Klassificering

Det går att särskilja två grupper av finita tillståndsmaskiner: igenkänningsmaskiner och översättningsmaskiner.

Igenkänningsmaskiner

En igenkänningsmaskin matas med ett indata i någon form och meddelar sedan omvärlden om detta indata var korrekt eller ej enligt något kriterium. En igenkänningsmaskin används till exempel till att kontrollera att en sats skriven i ett formellt språk (se formell grammatik) är korrekt och välformad.

Översättningsmaskiner

Översättningsmaskiner används för att översätta ett indata från en symboluppsättning till en annan. Man kan särskilja två olika typer, Moore-maskiner och Mealy-maskiner.

Moore-maskiner

En Moore-maskin använder endast ingångshändelser. Detta innebär att när en tillståndsförändring inträffar i en Moore-maskin så produceras också en del av resultatet av systemets arbete i samband med övergången. Vilket resultat som produceras beror endast av vilket tillstånd som övergången sker till.

Exempel: En hissdörr öppnas. Tillståndsmaskinen för hissdörrens beteende övergår från tillståndet Stängd till tillståndet Öppen. Samtidigt tänds belysningen inne i hissen

Mealy-maskiner

En Mealy-maskin använder endast indatahändelser. Detta innebär att när en tillståndsförändring inträffar i en Mealy-maskin så produceras också en del av resultatet av systemets arbete i samband med övergången. Vilket resultat som produceras beror, i motsats till Moore-maskinen, på vilket indata som ger upphov till övergången i kombination med vilket tillstånd som övergången sker till.

Exempel: En hissdörr öppnas. Tillståndsmaskinen för hissdörrens beteende övergår från tillståndet Stängd till tillståndet Öppen. Samtidigt tänds belysningen inne i hissen om den öppnas manuellt. Om det är hissens egen dörrmotor som öppnar dörren tänds inte lampan.

I praktiken används ofta en mix av dessa två maskintyper för översättning.

Deterministiska och icke-deterministiska finita tillståndsmaskiner

Man skiljer även mellan deterministiska och icke-deterministiska tillståndsmaskiner.

• En deterministisk finit tillståndsmaskin har exakt en definierad övergång för varje tillstånd för varje indata som är möjligt (korrekt) för detta tillstånd.
• För en icke-deterministisk finit tillståndsmaskin kan det finnas flera olika övergångar för ett givet tillstånd och ett givet korrekt ingångsdata.

Logiken för en finit tillståndsmaskin

Nästa tillstånd och nästa utdata för en finit tillståndsmaskin är en funktion av det aktuella indatat och det aktuella tillståndet.

Matematisk modell

Det finns ett flertal definitioner av finita tillståndsmaskiner beroende på vilken typ man talar om

En igenkännarmaskin är en kvintupel (femställig symbolföljd) <Σ, S, s0, δ, F>, där:

• Σ är det som kallas maskinens indataalfabete (en ändlig icke-tom mängd av symboler)
• S är en ändlig icke-tom mängd av tillstånd
• s0 är det så kallade starttillståndet, ett element i S. Maskinen befinner sig alltså i tillståndet s0 när den startas.
• δ är tillståndsövergångsfunktionen: δ = S x Σ → S
• F är mängden av möjliga sluttillstånd, en (möjligen tom) [delmängd] av S

Även om en igenkännarmaskin saknar formell utdatafunktion (se nedan), så finns den där implicit - en boolesk funktion som returnerar Sant eller Falskt beroende på om indatat accepterades eller ej.

En översättarmaskin är en sextupel (sexställig symbolföljd) <Σ, Γ, S, s0, δ, ω>, där:

• Σ är det som kallas maskinens indataalfabete (en ändlig icke-tom mängd av symboler)
• Γ är det som kallas maskinens utdataalfabete (en ändlig icke-tom mängd av symboler)
• S är en ändlig icke-tom mängd av tillstånd
• s0 är det så kallade starttillståndet, ett element i S. Maskinen befinner sig alltså i tillståndet s0 när maskinen startas.
• δ är tillståndsövergångsfunktionen: δ: S x Σ → S
• ω är utdatafunktionen

Om utdatafunktionen är en funktion av ett tillstånd och av indataalfabetet (ω: S x Σ → Γ) är maskinen en Mealy-maskin.

Om utdatafunktionen enbart beror på ett tillstånd (ω: S → Γ) är maskinen en Moore-maskin.

Optimering

Att optimera en finit tillståndsmaskin innebär att man söker den maskin med minsta möjliga antal tillstånd som utför samma funktion. Detta kan utföras med så kallade färgläggningsalgoritmer.

Källor

• Booth, Taylor L. (1967). Sequential Machines and Automata Theory (1st). New York: John Wiley and Sons, Inc. Library of Congress Card Catalog Number 67-25924