Sector
  • Havo bovenbouw
  • Vwo bovenbouw
Vakgebied
  • Informatica
Leerplankundig thema
  • Schoolexamen
  • Handreiking

Subdomein B3: Automaten

15-2-2018

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.png Figuur 5: Snoepuitgifte in de vorm van een eindige automaat

In dit voorbeeld zijn alle overgangen deterministisch: bij een gegeven input ​kan maar één overgang plaatsvinden (met 100% kans). In een nondeterministische eindige automaat spelen kansprocessen een rol: er zou bijvoorbeeld bij iedere muntinworp een kans kunnen zijn dat de munt niet geregistreerd wordt en de toestand niet verandert.

Als een (gewenst) systeem als eindige automaat is beschreven, kan vervolgens aan de hand van die beschrijving een algoritme opgesteld worden.