Les 3 & 4 - Toepassing eindige automaten

• Informatica
• Middelbare school
• havo, vwo
• Leerjaar 4-6

Eindige automaten

Toepassen eindige automaat als generator

Leerdoel

Je kunt een eindige automaat toepassen als generator en voorbeelden geven hoe een eindige automaat als dusdanig kan worden ingezet.

Toestandsdiagram lift

Bekijk het toestandsdiagram wat
het gedrag van een lift beschrijft.

• Hoeveel toestanden zie je in
   dit diagram?

• En hoeveel transities?

Hoeveel toestanden en transities heb je nodig om dit toestandsdiagram te tekenen?

1. 3 toestanden en 6 transities
2. 6 toestanden en 3 transities
3. 3 toestanden en 9 transities
4. 9 toestanden en 3 transities

Toestandsdiagram lift

• Het diagram kent 3 toestanden
   (BG, 1 en 2)

• Het diagram kent 9 transities
   (alle pijlen)

Toepassingen eindige automaat

We hebben gezien dat een eindige automaat gebruikt kan worden om de toestanden van een fysiek apparaat weer te geven.

Twee andere toepassingen van eindige automaten zijn:

• Als generator
• Als controlemiddel

Eindige automaat als generator

Door transities te volgen en op te schrijven, ontstaat er een zin

Bijzondere eindtoestand:

• Je mag stoppen
  
• Je mag ook terug naar
   de begintoestand
  

Eindige automaat als generator

Welke zin is geldig?

A.  een kleine professor
B.  een kleine jonge professor floot
C.  de dunne vogel vertelde
D.  de jonge poes dronk en
      de dunne kapitein

Welke zin is geldig?

1. een kleine professor
2. een kleine jonge professor floot
3. de dunne vogel vertelde
4. de jonge poes dronk en de dunne kapitein

Antwoord eindige automaat als generator

Welke zin is geldig?

A.  een kleine professor
B.  een kleine jonge professor floot
C.  de dunne vogel vertelde

D. de jonge poes dronk en

      de dunne kapitein

Toepassing: automatisch aanvullen

Toepassing: lorem ipsum-generator

Bedenk een
geldige zin.

Oefening: postcode-generator

Teken het schema van een eindige automaat voor het genereren van een Nederlandse postcode. De postcode moet bestaan uit vier cijfers. Het eerste cijfer mag geen 0 zijn. Na de vier cijfers komt er eerst een spatie. Daarna komen er twee hoofdletters.

Je kunt de eerste transitie op 2 manieren tekenen (zie hieronder). Maak het schema verder af. Gebruik voor elk symbool een aparte transitie.  

Hoeveel transities kent het diagram (tel de begintransitie niet mee)?

Uitwerking: Postcode-generator

Hiernaast zie je het schema van een eindige automaat voor het genereren van een
Nederlandse postcode. 

Het diagram kent:

• 8 toestanden
• 7 transities

Oefening: Amerikaanse postcodes

Postcodes in de Verenigde Staten bestaan uit vijf cijfers en werden ingevoerd in 1963. Deze vijf cijfers worden sinds 1983 gevolgd door een liggend streepje en vier extra cijfers, waarmee een verdere verfijning van de code werd bereikt tot op het niveau van huizenblokken.

Maak een schema om postcodes te genereren dat geschikt is voor alle Amerikaanse postcodes. Bedenk welke toestanden en transities je moet toevoegen. Let ook op de eindtoestanden!

Hoeveel eindtoestanden kent het schema?

Uitwerking: Amerikaanse postcodes

Hiernaast zie je het schema van een eindige automaat voor het genereren van een
Amerikaanse postcode. 

Het diagram kent:

• 11 toestanden,
    waarvan 2 eind
• 10 transities

Oefening: Klasnamen-generator

Het Alan Turingcollege is een school voor mavo, havo en vwo. Voor de klassen gebruiken ze namen als 2h1, 6v4 of 3m12. 

Opdracht: Teken het schema
van de eindige automaat
die hierbij hoort.

Oefening: Klasnamen-generator (2)

Hoe een klasnaam (2h1, 6v4 of 3m12) eruit ziet, is precies voorgeschreven:

• De naam van de klas begint met één cijfer voor het leerjaar (minimaal 1 en maximaal 6).
• Hierna komt één: letter 'm' (mavo), 'h' (havo) of 'v' (vwo).
• Afhankelijk van het onderwijstype, is het cijfer voorafgaande aan m: hoogstens een 4, aan h: hoogstens een 5 en aan v: hoogstens een 6.
• Na de letter van het onderwijstype kan er een oneindig aantal cijfers komen tussen de 1 en de 9. Bij twee of meer cijfers, mag vanaf het tweede cijfer wel een 0 gebruikt worden.

Teken het schema van de eindige automaat die hierbij hoort. Tip: teken eerst op papier een snelle schets. Denk dan na over het aantal eindtoestanden. Hoeveel zijn er daarvan?

Hoeveel transities zijn er minimaal nodig voor dit schema?

Uitwerking: Klasnamen-generator

Dit schema kan klasnamen
als 2h1, 6v4 of 3m12
genereren.

Het bevat 9 transities.

Afsluitende vraag

Met de eindige automaat van de vorige oefening is het mogelijk om oneindig veel verschillende klasnamen te genereren. Het aantal cijfers na de laatste letter is namelijk
onbeperkt.

Waarom spreken we dan toch
van een eindige automaat?

Waarom spreken we toch van een eindige automaat bij oneindig veel verschillende resultaten?

1. Er is een eindig aantal transities
2. Er is een eindig aantal toestanden
3. Er is een geldige begin- en eindtoestand
4. We spreken in dit geval van een oneindige automaat

Antwoord afsluitende vraag

Het woord 'eindig' in eindige automaat slaat op het aantal toestanden, niet op het aantal mogelijke uitkomsten.

Een eindige automaat heeft
altijd een eindig aantal
toestanden (zeven in dit geval). 

Leerdoel gehaald?

Je kunt een eindige automaat toepassen als generator en voorbeelden geven hoe een eindige automaat als dusdanig kan worden ingezet.

Voor de volgende les

Fundament

• Lees B3 - hoofdstuk
   2.1 en 2.2 door.

Eindige automaten

Toepassen eindige automaat als controlemiddel

Leerdoel

Je kunt een eindige automaat toepassen als controlemiddel en voorbeelden geven hoe een eindige automaat als dusdanig kan worden ingezet. Ook

kun je wat vertellen over de beperkingen van een eindige automaat zijn.

Eindige automaat als controlemiddel

Naast teksten genereren kan een eindige automaat ook teksten controleren. Bij de transities staat dan welke tekens toegestaan zijn.

• Ga een stuk tekst af.
• Volg voor ieder karakter
   de juiste transitie.
• Geen transitie? Dan
  ‘voldoet’ de tekst niet.

Eindige automaat als controlemiddel

Hoeveel van de volgende 7 teksten zullen worden geaccepteerd door de automaat?

ADCBE, ABEF, CBDADC, 

AEFFFFFFFFFFFFFF,

DAEF, CBADEF, 

CBDCBDAE

Hoeveel van de teksten wordt geaccepteerd door de automaat?

1. 3
2. 4
3. 5
4. 6

4 teksten worden geaccepteerd

ADCBE

ABEF
CBDADC

AEFFFFFFFFFFFFFF

DAEF
CBADEF

CBDCBDAE

Toepassing: online formulier

Controleren bij een webshop of je invoer juist is. 

• Bevat tekst in het e-mailveld een @ en een .?
• Bevat het tweede telefoonveld negen cijfers?
• Bestaat het adres uit een combinatie van
   letters en cijfers?

Oefening: mobiel nummer

Teken het schema van de eindige automaat waarmee een Nederlands mobiel telefoonnummer gecontroleerd kan worden. Ga ervan uit dat elk telefoonnummer begint met +31, 0031 of met een 0. Daarna volgen er precies 9 cijfers. Bedenk zelf welke cijfers zijn toegestaan. 

Hoeveel transities kent het diagram (tel de begintransitie niet mee)

Uitwerking: mobiel nummer

Hiernaast zie je het schema van een eindige automaat voor het controleren van een Nederlands mobiel nummer. 

Het diagram kent: 11 toestanden en 12 transities.

Automaat voor woonplaats?

Is het zinvol om voor de controle van de woonplaats een eindige automaat te gebruiken. Waarom wel / niet?

Is het zinvol om voor de controle van de woonplaats een eindige automaat te gebruiken?

1. Ja, dit werkt hetzelfde als bij een telefoonnummer
2. Ja, een automaat gebruiken is altijd zinvol
3. Nee, een woonplaats is niet uniek genoeg
4. Nee, een automaat kan niet tellen

Waarom geen automaat voor woonplaats?

Er zijn erg veel mogelijke woonplaatsen. Je kunt dus niet controleren op afzonderlijke woonplaats. Bovendien bevat iedere woonplaats letters, dat is dus ook geen uniek kenmerk. Met een eindige automaat is het niet mogelijk om te tellen, je kunt dus niet zeggen: invoer van 1 teken, of van 100+ tekens, is niet toegestaan.

Controle voor een woonplaats kan zijn: input niet leeg, bestaat uit ten minste 2 letters. Maar dit is dus geen automaat.

Beperkingen van een eindige automaat

Eindige automaten kennen een aantal beperkingen:

• Alleen toepasbaar voor eenvoudige algoritmen
• Voor sommige toepassingen onmogelijk

Een eindige automaat heeft geen geheugen, daarom niet toepasbaar op:

• HTML, want je moet onthouden welke tags er ‘open’ zijn
  
• Rekensommen, want je moet onthouden welke haakjes er ‘open’ zijn

Automaat voor HTML-elementen?

Wat maakt de onderstaande eindige automaat waarmee je HTML-elementen kunt controleren onvolledig?

Wat maakt de eindige automaat waarmee je HTML-elementen kunt controleren onvolledig?

1. Je kunt er maar een HTML-element per keer mee controleren
2. De automaat kan niet controleren of het groter-dan-teken wordt afgesloten
3. De automaat kan niet controleren of de start- en endtag hetzelfde zijn
4. Je kunt niet zien welk HTML-element er op dit moment gecontroleerd wordt

Waarom geen HTML-elementenautomaat ?

De automaat begint door de groter-dan- en kleiner-dan-tekens te controleren, met tussen de haakjes letters voor de naam van het element. Daarna wordt de inhoud gecontroleerd. Ten slotte worden de haakjes weer gecontroleerd.

 
Maar wanneer de eindige automaat 

bij de 'eindtag'-toestand is beland, 

'weet' de automaat niet meer welke 

begintag er is gekozen.

Eindige automaten en flexibiliteit

Een eindige automaat vertoont altijd hetzelfde gedrag, gewone computers, zoals smartphones, zijn flexibel.

Toch hebben we tal van toepassingen van nuttige toepassingen gezien waarin eindige automaten worden ingezet.

Welke toepassingen van een eindige automaat uit de praktijk hebben we allemaal gezien afgelopen lessen?

Noem een toepassing van een eindige automaat uit de praktijk.

Eindige automaten in de praktijk

Eindige automaten vinden praktische toepassingen in:

• Het modelleren van de werking van eenvoudige apparaten zoals   verkeerslichten, liften en spelersgedrag in games.
  
• Het genereren of aanvullen van zinnen, woorden of postcodes.
  
• Het controleren of teksten voldoen aan specifieke structuren. Dit is essentieel is voor het waarborgen van consistentie en validiteit.

Leerdoel gehaald?

Je kunt een eindige automaat toepassen als controlemiddel en voorbeelden geven hoe een eindige automaat als dusdanig kan worden ingezet. Ook

kun je wat vertellen over de beperkingen van een eindige automaat zijn.

Voor de volgende les

Fundament

• Lees B3 - hoofdstuk
   2.3 en 2.4 door.
• Maak vraag 4, 5 en 6 
   van hoofdstuk 2.3.
• Maak vraag 1 
  van hoofdstuk 2.4.