Eindigetoestandsautomaat

Een eindigetoestandsautomaat (in het Engels: finite-state automaton, veelal afgekort tot FA, of finite-state machine, afgekort tot FSM) is een abstract, wiskundig model voor het gedrag van een systeem waarbij het model bestaat uit een eindig aantal toestanden, overgangen tussen die toestanden en acties.

In de tekening hiernaast is een FA te zien met vijf toestanden X₀, ..., X₄, aangegeven met cirkels, tien overgangen tussen de vijf toestanden elk aangegeven door een doorgetrokken lijn met een richtingspijl en de twee acties 0 en 1 die zijn aangegeven als label bij de doorgetrokken gerichte lijnen tussen de toestandsovergangen. Van de tien overgangen beginnen en eindigen er twee in dezelfde toestand, dit zijn lussen ofwel self-loops.

De begintoestand wordt vaak aangegeven met een uit het niets inkomende pijl en accepterende eindtoestanden hebben vaak een dubbele cirkel. In de tekening is X₀ de begintoestand. De accepterende eindtoestand (meerdere accepterende eindtoestanden zijn mogelijk, zie verderop) in de figuur is X₄.

Eindigetoestandsautomaten worden onder meer toegepast in de theorie van berekenbaarheid in de wiskunde en in formele talen in de informatica. Eindigetoestandsautomaten worden vaak gerepresenteerd als grafen en beschrijven een klasse van formele talen die reguliere talen heten. De laatste decennia zijn er ook in andere vakgebieden, zoals in de economie, biologie en taalkunde, modellen ontwikkeld die gebruikmaken van dit basismodel.