Heading

Er wordt tegenwoordig veel gepraat over Finite State Machines in JavaScript-land.

Er is een populaire library genaamd XState, met meer dan 11000 sterren op GitHub, waar ik de laatste tijd tegenaan loop, en ik blijf er maar over lezen op Twitter en andere plaatsen. Het is een heel cool project.

Ik heb voor het eerst kennisgemaakt met Finite State Machines en Automata op de middelbare school, 20 jaar geleden, en daarna kwam ik ze weer tegen in mijn cursus Digital Design aan de universiteit.

Deze cursus ging over het coderen van informatie, booleaanse algebra, combinatorische netwerken, sequentiële schakelingen, sequentiële toestandsmachines, rekenkundige schakelingen, VHDL, en meer.

Ik vond het onderwerp Finite State Machines toegepast op Frontend Engineering nogal verbazingwekkend, en ik ging terug naar mijn oude boeken om te zien of ik er een goede uitleg van kon vinden.

Ik vond veel informatie, en natuurlijk worden dingen in tekstboeken ingewikkelder gemaakt dan nodig is (IMHO). Ik hou ervan om dingen te vereenvoudigen, en ik besloot om een beetje uitleg te schrijven voor normale mensen, niet theoretisch of iets gemaakt om een examen te halen. Dingen die je in de echte wereld kunt toepassen.

State Machines

Voordat ik inga op wat een Finite State Machine is, wil ik eerst introduceren wat een State Machine is.

De wereld is gevuld met state machines. Je ziet ze overal, maar misschien heb je ze niet als zodanig gezien. Na het lezen van deze tutorial, weet ik zeker dat je objecten in de echte wereld zult aanwijzen en tegen je vrienden zult zeggen “dat is een toestandsmachine” (afhankelijk van het nerdy niveau van je vrienden).

Het meest populaire en meest voorkomende voorbeeld is een verkeerslicht.

Op elk moment in de tijd heeft een verkeersmast een gedefinieerde toestand. Typisch, het is ofwel:

• heeft het groene licht aan, en de andere 2 lichten uit
• heeft het rode licht aan, en de andere 2 lichten uit
• heeft het gele licht aan, en de andere 2 lampjes uit

(Sommige semaforen zijn iets anders, maar dat maakt ons voor dit voorbeeld niet uit)

In State Machines-terminologie wordt het aan of uit zijn van lampjes output genoemd.

Elk van deze 3 scenario’s wordt toestand genoemd. De verkeers-semafoor zal van toestand veranderen wanneer het een input ontvangt, meestal gewoon een vaste timer die bepaalt hoe lang de verkeerslichten groen, geel en rood moeten zijn.

De timer in dit geval is de input van het systeem. Sommige semaforen hebben een knop die voetgangers kunnen indrukken om de auto’s op rood te laten springen, en dat zou een andere input zijn.

In een toestandsmachine kan de toestand alleen veranderen (en hebben we een overgang) als reactie op een input.

Finite State Machines

Onze toestandsmachine voor verkeerslichten is eindig omdat we een eindig aantal toestanden hebben.

Sommige systemen kunnen een oneindig aantal toestanden hebben.

Zoals het model van het wereldecosysteem, of het leven van een insect. We kunnen het niet definiëren in een eindig aantal toestanden.

Maar stoplichten? Dat is een eenvoudig ding, en het heeft 3 toestanden, zoals we hierboven al zeiden.

Er zijn nog veel meer voorbeelden van eindige-toestandsmachines die we zouden kunnen gebruiken:

• een verkoopautomaat
• een tourniquet voor de ingang van de metro
• een verwarmingssysteem
• een geautomatiseerd metrosysteem
• een zelfrijdend autosysteem
• een lift

Maar laten we het bij ons verkeerslichtenvoorbeeld houden, dat is heel eenvoudig en we kunnen er gemakkelijk over redeneren.

Modelleren van een toestandsmachine

Verkeerslichten bestaan natuurlijk niet op zichzelf. Dat is een andere eindige toestandsmachine, die meerdere verschillende eindige toestandsmachines bevat voor elk verkeerslichtapparaat dat is geïnstalleerd voor elke kant van elke weg van een kruispunt, die synchroon werken.

Denk er nu niet over na. Laten we ons concentreren op 1 enkele verkeersmemafoor.

Zoals we hierboven al zeiden, hebben we 3 toestanden, die groen, rood, geel kunnen oproepen.

We hebben een begintoestand. Laten we zeggen dat onze verkeerslichten, wanneer we ze resetten, beginnen in de green status.

We hebben een timer die na 50 seconden groene status, de semafoor verplaatst naar de yellow status. We hebben 8 seconden yellow toestand, dan gaan we naar de red toestand, en daar blijven we 32 seconden zitten, want die weg is secundair en verdient minder tijd van groen. Hierna gaat de semafoor weer terug naar de groene toestand en de cyclus gaat oneindig door, totdat de elektriciteit stopt en de semafoor reset als hij weer stroom krijgt.

In totaal hebben we een cyclus van 90 seconden.

Dit is hoe we het kunnen modelleren:

We kunnen het ook modelleren met een toestandovergangstabel, die laat zien in welke toestand de machine zich op dat moment bevindt, wat de invoer is die hij ontvangt, wat de volgende toestand is, en de uitvoer:

State	Input	Next state	Output
Groen	Timer 50s	Geel	Groen lampje aan, andere uit
Geel	Timer 8s	Rood	Geel lampje aan, andere uit
Rood	Timer 32s	Groen	Rood licht aan, andere uit

In ons eenvoudige geval, hebben we, gegeven elke toestand van de machine, slechts één logische toestand om naartoe te gaan, dus de tabel en de grafiek die ik heb gemaakt zijn heel, heel eenvoudig.

Maar als je systeem complexer wordt, is het erg handig om zulke diagrammen en analyses te hebben, omdat je dan veel gemakkelijker over je toepassing kunt redeneren dan door alles gewoon in je hoofd te houden.

Een eindige toestandsmachine met complexere toestandsovergangen

Het bovenstaande voorbeeld is erg eenvoudig. Laten we nu een andere Finite State Machine modelleren.

Ons scenario uit de echte wereld is het volgende: we hebben een huis, met een deur, 2 knoppen en 3 lampen.

In de standaardtoestand zijn de lampen allemaal uit.

Wanneer je het huis binnenkomt, kun je op een van de 2 drukknoppen drukken die je hebt, p1 of p2. Als je op een van die knoppen drukt, gaat het l1 licht aan.

Stel je voor dat dit het ingangslampje is, en dat je je jas uit kunt doen. Als je klaar bent, beslis je welke kamer je in wilt (keuken of slaapkamer, bijvoorbeeld).

Als je op de knop p1 drukt, gaat l1 uit en l2 gaat aan. Als u in plaats daarvan op de knop p2 drukt, gaat l1 uit en l3 aan.

Druk je nog een keer op een van de 2 knoppen, p1 of p2, dan gaat het licht dat op dat moment brandt uit, en zijn we weer terug bij de begintoestand van het systeem.

Deze Finite State Machine is iets complexer dan de eerste, omdat we deze keer meerdere routes kunnen hebben, afhankelijk van de invoer.

Laten we dit eens modelleren.

We hebben in principe 4 toestanden:

• geen lichten aan
• l1 aangezet
• l2 ingeschakeld
• l3 ingeschakeld

We hebben 2 ingangen:

• p1
• p2

Als we uitgaan van de begintoestand, en we proberen alles te modelleren wat er kan gebeuren afhankelijk van hoe de ingangen in de loop van de tijd worden geactiveerd, krijgen we als resultaat:

Wat kan worden samengevat met behulp van deze tabel:

State	Input	Next state
geen lichten aan	p1 ingedrukt	l1 aangezet
geen lichten aan	p2 ingedrukt	l1 aangezet
l1 aangezet	p1 ingedrukt	l2 aangezet
l1 aangezet	p2 ingedrukt	l3 aangezet
l2 aangezet	p1 ingedrukt	geen licht aangezet
l2 aangezet	p2 ingedrukt	geen lichten aangezet
l3 aangezet	p1 ingedrukt	geen lichten aangezet
l3 aangezet	p2 ingedrukt	geen lampjes aangezet

Dat is een korte en simpele uitleg, maar misschien laat het dingen “klikken”.

Meer computers tutorials:

• Finite State Machines
• Het decimale getallenstelsel
• Het binaire getallenstelsel
• Het omzetten van getallen van decimaal naar binair
• Lijst met afdrukbare ASCII-tekens
• Niet-afdrukbare ASCII-tekens
• Hoe maak je verbinding met een Raspberry Pi via een Mac
• Hoe zorg je ervoor dat de Raspberry Pi altijd hetzelfde IP-adres heeft
• Een zeer korte introductie in COBOL