Leertaak 2

Eindige automaten

Achtergrond

Eindige automaten zijn abstracte machines waarmee we het stapsgewijs doorlopen van strings kunnen modelleren. Zo'n automaat heeft een aantal inwendige toestanden. De invoer van een string begint in een aangewezen starttoestand. Bij het achtereenvolgens lezen van de inputsymbolen springt de automaat van de ene toestand naar de andere, vastgelegd door een zogenaamde overgangsfunctie die bij elke toestand en invoersymbool een volgende toestand voorschrijft. Een string wordt geaccepteerd als de machine na het doorlopen van de string in een tevoren aangewezen eindtoestand is gekomen. Zo hoort er bij elke eindige automaat een taal: de verzameling van geaccepteerde strings.

In bepaalde gevallen is een automaat een handige methode om een taal te beschrijven. Zo is het bijvoorbeeld heel gemakkelijk om uit een automaat voor een bepaalde taal een andere automaat te maken die het complement van die taal karakteriseert.

We breiden de automaten uit met nondeterminisme: voor een symbool zijn zo meerdere toestandsovergangen mogelijk. Ook kunnen we spontane toestandsovergangen, dus zonder dat er iets gelezen wordt, toelaten. Nondeterministische automaten geven veel uitdrukkingsvrijheid bij het karakteriseren van talen. Veel constructies zijn op een elegante en inzichtelijke manier te realiseren via nondeterministische automaten.

Nondeterministische constructies staan doorgaans dicht bij de informele, intuïtieve taalbeschrijving. Deterministische automaten passen weer beter bij de wijze waarop machinale taalherkenning wordt gedaan. Er is gelukkig een methode om een nondeterministische automaat om te zetten naar een deterministische automaat die dezelfde taal herkent.

Leerdoel

Na het voltooien van deze taak kun je

• onderstaande kernbegrippen (zie 'Instructie') verklaren;
• berekeningen in eindige automaten beschrijven;
• bij een gegeven eindige automaat de geaccepteerde taal beschrijven;
• een eindige automaat construeren aan de hand van een informele taalbeschrijving;
• een nondeterministische automaat (met lambda-overgangen) transformeren naar een equivalente deterministische automaat.

Instructie

1. Lees p. 145-177. Kernbegrippen:
   • deterministische eindige automaat (DFA)
   • overgangsfunctie, overgangstabel, toestandsdiagram
   • configuratie, berekening, acceptatie, taal bij de automaat
   • nondeterministische eindige automaat (NFA)
   • lambda-overgang
   • vewijderen van niet-determinisme
   • lambda-afsluiting, input-overgangsfunctie
2. Werk opgave 2 (p. 184) uit.
3. Doe de opdrachten 8 en 15.
4. Voer opdracht 36 uit.

Product

• Bechrijving van de geaccepteerde talen van de automaten.
• Automaten die de gegeven talen accepteren.
• Analyse van de nondeterministische automaat; transformatie naar een deterministische variant.

Reflectie

• Heb je de antwoorden voorzien van een toelichting?
• Zou je desgevraagd het toestandsdiagram van je automaten kunnen omzetten naar een beschrijving zoals in definitie 5.2.1?
• Geef je bij de geconstrueerde automaten een (bedoelde) interpretatie van elke toestand?