Eindigetoestandsautomaat
De eindigetoestandsautomaat (Engels: finite state machine) of kortweg "eindige automaat" is de abstracte voorstelling van een systeem als een machine die zich in verschillende, discreet te onderscheiden toestanden kan bevinden, en onder bepaalde condities van de ene toestand in de andere overgaat.
De grafische weergave van een eindige automaat wordt een toestandsdiagram genoemd.
Als computationeel model kan een eindige automaat het dynamische gedrag van het voorgestelde systeem nabootsen. Zo'n model kan dan antwoord geven op vragen als "Hoe lang blijft het systeem gemiddeld in toestand A?", "Hoe groot is de kans dat het systeem binnen tijd t in toestand A terecht komt?" en "Welke transitiepaden komen vaak voor? En welke zijn juist uiterst zeldzaam?".
Modelleerconcepten
Een eindigetoestandsautomaat is een abstract netwerk met toestanden (Engels: states) als knopen en toestandsovergangen of kortweg overgangen (Engels: transitions) als takken. De toestanden waarin het gemodelleerde systeem zich kan bevinden worden weergegeven door cirkelvormige toestandsymbolen. In deze cirkels wordt voor één of meer variabelen (corresponderend met relevante factoren binnen het systeem) een specifiek waardebereik aangegeven, bijvoorbeeld "X = 0" of "Y > 0,75". Deze variabelen worden toestandsvariabelen genoemd. De overgangen tussen toestanden worden met pijlen aangegeven.
In een toestandsdiagram dat een deterministische eindigetoestandsautomaat weergeeft wordt elke pijl A → B gelabeld met een voorwaarde in termen van procesvariabelen: variabelen die veranderen als functie van de tijd en de waarde van de toestandsvariabelen. De tijd t is dus altijd een procesvariabele.
In een toestandsdiagram dat een probabilistische eindigetoestandsautomaat weergeeft wordt elke pijl A → B gelabeld met een kanswaarde tussen 0 en 1 die weergeeft hoe waarschijnlijk het is dat het systeem vanuit toestand A overgaat naar toestand B. Zo'n eindigetoestandsautomaat wordt een Markovketen genoemd.
Voorbeeld
Het onderstaande toestandsdiagram specificeert het gedrag van een toeritdoseerinstallatie voor een oprit met twee rijstroken en dus ook twee doseerlichten. Het diagram laat zien dat het systeem in vijf verschillende toestanden kan verkeren. Deze toestanden worden gedefinieerd door de kleur van de twee verkeerslichten (toestandsvariabelen L1 en L2) en het nummer van de rijstrook die het laatst "groen licht" kreeg (toestandsvariabele N). Deze derde variabele is nodig omdat het systeem anders na de toestand "beide lichten rood" niet zou "weten" welke rijstrook aan de beurt is.
De pijlen in het diagram zijn gelabeld met de voorwaarden waaronder het systeem in een nieuwe toestand overgaat. Daarbij zijn twee factoren van belang: de tijd Δt (in seconden) die is verstreken sinds de laatste gebeurtenissen en de rijsnelheid v (in km/h) van de voertuigen op de weg.
Het model laat zien dat beide doseerlichten op groen blijven staan zolang de rijsnelheid op de snelweg ten minste 70 km/h is. Daalt die snelheid onder dit niveau, dan treedt het doseermechanisme in werking. De lichten worden dan bij toerbeurt 3 seconden lang groen (genoeg om één voertuig door te laten), waarna beide lichten weer enige tijd op rood staan. De roodtijd wordt langer naarmate de rijsnelheid lager is, tot een maximum van 40 seconden.
Van dit voorbeeld bestaat een uitwerking tot een computationeel model in Excel.
Toepassing
Eindige automaten worden vooral gebruikt bij het ontwerpen van een technisch systeem. Ontwerpers kunnen dan het gedrag van het gemodelleerde systeem onder verschillende omstandigheden te bestuderen. Door procesvariabelen op diverse manieren van waarde te laten veranderen kan worden nagegaan of het systeem naar wens functioneert. Zo kan m.b.v. het hier gegeven voorbeeldmodel worden nagegaan hoeveel voertuigen per uur worden toegelaten bij verschillende rijsnelheden. Om de effectiviteit van de toeritdoseringsinstallatie te kunnen bepalen zou het model moeten worden uitgebreid met vergelijkingen die de rijsnelheid v mede afhankelijk maken van het aantal toegelaten voertuigen.
