Tillståndsmaskin

Från Rilpedia

Hoppa till: navigering, sök
Wikipedia_letter_w.pngTexten från svenska WikipediaWikipedialogo_12pt.gif
rpsv.header.diskuteraikon2.gif

En Tillståndsmaskin (eng State Machine eller Automaton) är en abstrakt modell som används bland annat till att beskriva beteenden i mjukvara, inom hårdvarudesign, beräkningsteori och språkvetenskap. Användningsområdena är många, men generellt kan man säga att 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.

Normalt ser man begreppet Tillståndsmaskin såsom synonymt med ändlig tillståndsmaskin (eng Finite State Machine eller Finite Automaton) eftersom en tillståndsmaskin måste ha ett ändligt antal tillstånd för att vara praktiskt användbar.

Innehåll

Informell beskrivning

En typisk 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 eller Stängd
Övergångar: Öppna eller Stäng

Man säger att en tillståndsmaskin alltid befinner sig i ett tillstånd, och om ett visst villkor uppfylls så övergår tillståndsmaskinen till ett annat tillstånd. Om till exempel tillståndsmaskinen för Dörr ovan befinner sig i tillståndet Stängd och någonting får villkoret för övergången Öppna att inträffa (dvs, någon öppnar dörren) så övergår tillståndsmaskinen till tillståndet Öppen.

Man illustrerar oftast tillståndsmaskiner med bubblor som representerar tillstånd och pilar som representerar övergångar. Man skriver då villkoret för övergången vid pilen:

Grafisk bild av tillståndsmaskin för Dörr

Vi inser här att vissa övergångar bara är meningsfulla för vissa tillstånd. Vi inser också att vi lätt kan införa tillståndet Låst till modellen för dörr.

När man arbetar med tillståndsmaskiner uppstår ofta delikata frågor. Man kan till exempel fråga sig om det ska finnas en övergång till Låst när dörren är i tillståndet Öppen. I praktiken är det ju möjligt att låsa en öppen dörr, men logiskt sett är det kanske inte meningsfullt.

Grafisk bild av utökad tillståndsmaskin för Dörr

Ovan ser vi en bild av en utökad tillståndsmaskin för Dörr där tillstånden Låst och Fel har införts. Denna tillståndsmaskin är inte speciellt förlåtande, då dörren fastnar i tillståndet Fel om man antingen försöker låsa eller låsa upp den när den är öppen, eller om man försöker öppna eller stänga den när den är låst. Det kanske finns ett bättre sätt att hantera mänskliga felbeteenden på?

Grafisk bild av korrekt tillståndsmaskin för Dörr

Här ser vi en mer förlåtande tillståndsmaskin för en dörr. En tillståndsmaskin som hanterar felbeteenden eller felaktig input förlåtande sägs vara robust.

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

Modell för Dörr
Tillstånd:  Öppen, Stängd eller Låst
Övergångar: Öppna, Stäng, Lås och Lås upp

Formell beskrivning

(Detta är en fri översättning av texten under Finite State Machine i engelska Wikipedia [1].)

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 beteenden 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 har gått sedan det system som tillståndsmaskinen modellerar startades - dvs, den reflekterar de stimuli som systemet har utsatts för från att det startades fram till nuet.
  • En övergång indikerar en tillståndsändring, och den 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 måste inträffa vid 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

En Moore-maskin använder endast ingångs-hä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.

Ett 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 indata-hä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.

Ett 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 lampan inte

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 bakom en Finit Tillståndsmaskin

Nästa tillstånd och utdata från en finit tillståndsmaskin är en funktion av det nuvarande indatat och 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 finaltillstå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.

Personliga verktyg
På andra språk