toestandsmachines

Een toestandsmachine, in de informatica vaak een finite state machine genoemd, is een abstract model van berekening dat gedrag beschrijft als een verzameling toestanden. Een machine bevindt zich in één toestand tegelijk en kan bij bepaalde invloeden (invoer) van toestand veranderen via overgangfuncties. Sommige uitvoer wordt geproduceerd afhankelijk van de toestand of van zowel toestand als invoer.

Er bestaan deterministische toestandsmachines (DFA) en niet-deterministische toestandsmachines (NFA). Daarnaast worden twee hoofdtypen uitgangsgedrag onderscheiden: Moore-machines, waarbij de uitvoer uitsluitend afhangt van de huidige toestand, en Mealy-machines, waarbij de uitvoer ook afhangt van de huidige invoer.

Formele structuur: een toestandsmachine bestaat uit een eindige verzameling toestanden S, een alfabet van invoer I, een overgangsfunctie δ: S × I → S, een beginstaat s0 ∈ S; en optioneel een uitvoerfunctie λ: S → O (Moore) of λ: S × I → O (Mealy).

Veelvoorkomende toepassingen: besturingssystemen en protocollen (bijv. netwerkhandshakes), gebruikersinterfaces, embedded-systemen en hardwareontwerp. In softwareontwikkeling worden toestandsmachines gebruikt om sequentiële logica, dialoogstromen en lexers te modelleren. Een voorbeeld is een verkeerslicht dat overgaat tussen rood, groen en geel op basis van tijd of input.

Relatie met theorie: een finite automaton herkent formele talen die bekend staan als reguliere talen; ze zijn equivalent aan reguliere expressies in beschrijving. Ontwerp en verificatie maken gebruik van toestandsdiagrammen, tabellen en model checking om gewenste eigenschappen te verifiëren. Beperkingen omvatten de toestandsexplosie bij complexe systemen; grotere systemen vereisen hiërarchische of samengestelde benaderingen.

Implementatie: toestandsmachines kunnen softwarematig of als hardware (in logische poorten en flip-flops) worden gerealiseerd. Ze blijven populair vanwege hun duidelijkheid, voorspelbaarheid en eenvoudige testbaarheid.