Subdomein B3: Automaten

13 december 2019

Eindige automaten worden vaak gebruikt om het gedrag van een systeem te beschrijven.

Een eindige automaat is een systeem met:

  • een eindig aantal toestanden, waaronder een begintoestand;
  • mogelijk een of meer eindtoestanden;
  • een aantal regels die beschrijven tussen welke toestanden er een overgang mogelijk is en eventueel onder welke voorwaarden.

Een verkeerslicht in Nederland kent bijvoorbeeld drie toestanden: 'rood' (de begintoestand), 'oranje' en 'groen' en drie mogelijke overgangen: 'rood' → 'groen', 'groen' → 'oranje' en 'oranje' → 'rood'. In deze eindige automaat is er geen eindtoestand.

Vaak zijn bij een eindige automaat vanuit een toestand meerdere overgangen mogelijk en bepaalt de input welke overgang plaatsvindt, zoals in onderstaande voorbeeld van de muntinvoer van een snoepautomaat voor snoepjes van 25 cent zonder wisselgeld. De gekozen overgang hangt steeds af van de grootte van de inworp. Deze eindige automaat heeft de toestand '25 cent of meer' als eindtoestand.

automaat sub b3