Eindige automaten

Gepost door Adriaan Gijssen op 23 augustus 2017

Een boeiend nieuw onderwerp in het vernieuwde examenprogramma is 'eindige automaten'. Wat wordt hier precies mee bedoeld?

Laten we eens kijken naar een lift die mensen kan vervoeren. De lift gaat van en naar de begane grond en twee verdiepingen. De lift is ontworpen om het volgende te kunnen doen:

Het gedrag van de lift kunnen we beschouwen als een eindige toestandsautomaat. Dat is een apparaat dat zich in een bepaalde vaste toestand bevindt en dat kan overgaan naar een andere toestand. De lift bevindt zich in één van de drie vaste toestanden, dat zijn de verdiepingen waarop de lift stilstaat. De lift kan naar een andere toestand (een andere verdieping) overgaan.

In plaats van de term eindige toestandsautomaat gebruiken we meestal het kortere eindige automaat.

Eindige automaten kun je op een overzichtelijke manier weergeven in een schema. Het gedrag van de lift uit dit voorbeeld kunnen we zo weergeven:

De cirkels staan voor de drie toestanden van de lift: de verdiepingen waarheen de lift heen kan. BG is de begane grond. 1 is de eerste verdieping. 2 is de tweede verdieping. De pijlen geven aan welke toestandsovergangen mogelijk zijn. Een toestandsovergang noemen we een transitie.

Drie belangrijke reden waarom eindige automaten in de praktijk belangrijk zijn:

1. Inzicht in een probleem
Eindige automaten helpen je om een complex probleem helder en overzichtelijk te maken. Een voorbeeld daarvan is een druk kruispunt waar verkeerslichten worden geplaatst. Door een eindige automaat te ontwerpen zorg je voor een helder overzicht van alle verkeersstromen die tegelijk over de kruising mogen.

2. Veilig ontwerpen
Eindige automaten zijn ook een handig hulpmiddel om een apparaat, of een onderdeel daarvan, veilig te ontwerpen. Zo mag een wasmachine pas gaan werken als er water beschikbaar is. Een lift mag pas omhoog of omlaag als de deuren dicht zijn. Bij het ontwerpen van een eindige automaat wordt je gedwongen om alle toegestane toestanden in kaart te brengen.

3. Theoretische informatica
Ten slotte spelen eindige automaten een belangrijke rol in de theoretische informatica. Bij het onderdeel algoritmiek heb je gezien dat het belangrijk is om te bepalen of een algoritme efficiënt is. Ook heb je gezien dat niet elk probleem door een computer correct kan worden opgelost. Eindige automaten zijn een belangrijk hulpmiddel om de efficiëntie en correctheid van een algoritme te bepalen.

 

-- Share It --