Schatzoeken – Eindige automaat

Waar gaat activiteit 11 over?

Een eindigetoestandsautomaat (of korter: eindige automaat; Engels: finite-state machine) wordt gebruikt om een computer een rij tekens of gebeurtenissen te laten verwerken.

Een eenvoudig voorbeeld is wanneer je een telefoonnummer belt en te horen krijgt “Toets 1 voor …, toets 2 voor …, toets 3 wanneer u een medewerker wilt spreken.”. Jouw toetsindrukken zijn de invoer voor de eindige automaat aan de andere kant van de lijn. Soms is de dialoog eenvoudig, maar hij kan ook heel complex worden. Het komt soms voor dat je met bepaalde toetsindrukken weer terugkomt waar je al was, er zit dan een lus (loop) in de eindige automaat. Als dat gebeurt, is er een fout gemaakt in het ontwerp van het systeem; als beller kun je er behoorlijk tureluurs van worden!

Een ander voorbeeld is wanneer je geld opneemt bij een PIN automaat. Het programma in de PIN-automaat leidt je langs een reeks gebeurtenissen. Intern weet de automaat welke rijen gebeurtenissen mogelijk zijn via een eindige automaat. Iedere toets die je indrukt brengt de automaat in een andere toestand. Sommige toestanden hebben opdrachten voor de PIN-automaat, bijvoorbeeld “geef € 50 biljet”, “druk een bewijsje af” of “werp de bankpas uit”.

Er zijn computerprogramma’s die echt met de Nederlandse taal werken. Zulke programma’s kunnen zelf zinnen maken of iets doen met zinnen die door een gebruiker worden ingevoerd. In de zestiger jaren van de vorige eeuw schreef een computerdeskundige een beroemd geworden programma Eliza, genoemd naar Elize Dolittle, dat gesprekken kon voeren met mensen. Het programma deed zich voor als psychotherapeut en had openingszinnen als “Vertel me wat over je familie” en “Vertel me wat meer”. Hoewel het programma geen snars begreep van de zinnen die over en weer gingen, waren de zinnen zo goed dat sommige mensen het gevoel kregen met een echte psychotherapeut te spreken.

Computers blijven veel moeite houden met het begrijpen van natuurlijke taal maar met kunstmatige talen kunnen ze uitstekend overweg. Programmeertalen zijn belangrijke voorbeelden van kunstmatige taal. Computers lezen een programma geschreven in programmeertaal teken voor teken in en gebruiken dan een eindige automaat om het te vertalen naar hele eenvoudige taken die de computer kan uitvoeren.

Geschikt voor leeftijd: 9 jaar en ouder

Download activiteit 11 hier: Schatzoeken – Eindige automaat