eindigetoestandsmachines

Eindige toestandsmachines, ook bekend als finite state machines (FSM’s), zijn wiskundige modellen die systemen beschrijven die door een eindige set toestanden bewegen onder invloed van invoer. Een FSM bestaan meestal uit een finite aantal toestanden, een invoeralphabet, een overgangsfunctie, een starttoestand en, voor acceptatietypen, een verzameling accepteertoestanden. Het gedrag wordt bepaald door de huidige toestand en de ontvangen invoer.

Deterministische eindige toestandsmachine (DFA) levert bij elke combinatie van huidige toestand en invoer precies één volgende toestand op. Niet-deterministische eindige toestandsmachine (NFA) kan daarentegen meerdere mogelijke volgende toestanden toestaan, of zelfs geen enkele. Veel NFAs kunnen zonder verlies worden omgezet naar equivalent DFA’s.

Mealy- en Moore-machines bevinden zich op het gebied van uitvoergeneratie. Een Mealy-machine produceert uitvoer op basis van de huidige toestand en de invoer, terwijl een Moore-machine uitvoer produceert op basis van de huidige toestand alleen.

Formeel kan een DFA worden gedefinieerd als een vijfvoud (Q, Σ, δ, q0, F), waarbij Q een eindige toestandsverzameling is, Σ het invoeralphabet, δ: Q × Σ → Q de overgangsfunctie, q0 ∈ Q de begintoestand, en F ⊆ Q de accepteertoestanden. NFAs gebruiken δ: Q × Σ → P(Q). Mealy- en Moore-machines voegen respectievelijk een uitvoerfunctie toe.

Toepassingen van FSM’s zijn breed: lexicale analyse in compilers, protocol- en besturingssystemen, modellering van gebruikersinterfaces, hardwareontwerp (zoals controllers), en formale verificatie van sequentiële systemen. FSM’s bieden een vereenvoudigde maar krachtige beschrijving van deterministische sequentiële gedragspatronen.