Eindigetoestandsautomaat

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Een deterministische eindige automaat.

Een eindigetoestandsautomaat (in het Engels: finite-state automaton veelal afgekort tot FA) is een abstract, wiskundig model voor het gedrag van een systeem waarbij het model bestaat uit een eindig (dus: beperkt) aantal toestanden, overgangen tussen die toestanden en acties.

In de tekening hiernaast is een FA te zien met vijf toestanden aangegeven met een cirkel (X0, ..., X4), tien overgangen tussen de vijf toestanden elk aangegeven door een doorgetrokken lijn met een richtingspijl en de twee acties 0 en 1 die zijn aangegeven als label bij de doorgetrokken gerichte lijnen tussen de toestandsovergangen. Van de tien overgangen beginnen en eindigen er twee in dezelfde toestand, dit zijn lussen ofwel self-loops.

De begintoestand wordt vaak aangegeven met een uit het niets inkomende pijl en accepterende eindtoestanden hebben vaak een dubbele cirkel. In de tekening is X0 de begintoestand. De accepterende eindtoestand (zie verder) in de figuur is X4.

Eindigetoestandsautomaten worden onder meer toegepast in de theorie van berekenbaarheid in de wiskunde en in formele talen in de informatica. Eindigetoestandsautomaten zijn gebaseerd op grafen en beschrijven een klasse van formele talen die reguliere talen heten. De laatste decennia zijn er ook in andere vakgebieden, zoals in de economie, biologie en taalkunde, modellen ontwikkeld die gebruik maken van dit basismodel.

Twee basistypen[bewerken]

Er worden twee typen eindigetoestandsautomaten onderscheiden: de deterministische eindige automaten (DFA, van het Engelse deterministic finite automaton), en de niet-deterministische eindige automaten (NFA, van het Engelse nondeterministic finite automaton). Deze beide automatentypen zijn elk weliswaar aan verschillende regels onderworpen (zie hierna), maar beschrijven dezelfde klasse van talen. Een NFA is dan ook op mechanische wijze met behulp van een algoritme, de zogeheten subset-constructie, om te zetten naar een DFA die dezelfde (formele) taal representeert. DFA's zijn doorgaans sneller terwijl NFA's (veel) compacter qua geheugengebruik zijn, waardoor er een tijd versus ruimte afweging gemaakt kan worden.

Eindige automaten en reguliere talen[bewerken]

Herkenning en generatie[bewerken]

Zoals bij ieder model van berekenbaarheid (bijvoorbeeld de Turingmachine) wordt de werking van een automaat veelal beschreven in termen van het herkennen van een bepaalde, formele taal. Onder een formele taal T verstaat men een verzameling rijen van karakters (woorden), waarbij de karakters uit een strikt gedefinieerde verzameling komen. Een herkenner voor een dergelijke taal is een machine die een rij tekens kan inlezen en dan de vraag beantwoordt of die rij karakters gezamenlijk (d.w.z. in haar geheel) een woord is uit de taal T of niet. "Ja" staat hierbij voor herkenning, "nee" voor geen herkenning, weigering, of welke terminologie men hiervoor ook wenst te gebruiken.

Stel: in de tekening is X0 de begintoestand en X4 de accepterende eindtoestand. De rij karakters '1110' wordt dan geaccepteerd (we eindigen bij een rondgang in toestand X4), terwijl '1111' wordt afgewezen (we eindigen in een niet-accepterende toestand X0).

Een alternatieve gebruikswijze is dat men de automaat gebruikt om woorden die tot de taal T behoren te genereren. Daarbij gaat men tegengesteld te werk als bij een herkenner: uitgaande van de formele taalregels zoals die zijn beschreven door een automaat, worden woorden gecreëerd.

Reguliere talen[bewerken]

Eindige automaten herkennen een klasse van talen die bekendstaat als de klasse der reguliere talen. Dit zijn talen die qua structuur (d.w.z. voor wat betreft woord- en zinsopbouw) relatief eenvoudig zijn. Dat wil overigens niet zeggen dat het kleine of simpele talen zijn – een reguliere taal kan best oneindig veel woorden bevatten. Maar voor al die woorden geldt wel dat ze aan relatief simpele vormregels voldoen.

Een voorbeeld van een reguliere taal T met als alfabet Σ (= verzameling toegestane tekens) de verzameling {a, b, c}, is de verzameling van woorden die gevormd worden door de regels:

  • eerst 0 of meer keer een a,
  • dan ten minste één c,
  • vervolgens drie keer een a of een b,
  • dan 0 of meer keer een c,
  • en ten slotte de tekenrij abc.

Voorbeelden van woorden (strings) uit de taal T zijn dan ccbbbabc, aaaaaccabacabc, aacaaaabc, cbbbabc, aaccccccccccccccbabccabc en acaaacabc.

Daarentegen hoort het woord bcbaa niet in T thuis. Evenmin als aaaacaaaccab, ccde en aaaaaaabc.

Eindige automaten en grafen[bewerken]

Eindige automaten worden vrijwel altijd weergegeven als een graaf. De reden hiervoor is dat een graaf zo mooi past bij de manier waarop een reguliere taal werkt.

Een definitie van een reguliere taal bestaat uit een opsomming van vormregeltjes die afgewandeld worden om te beoordelen of een gegeven woord ook tot de taal behoort. Kan een woord netjes gelezen c.q. verwerkt worden met behulp van die regeltjes (of gevormd worden met behulp van die regeltjes), dan is het woord onderdeel van die beschreven taal. Anders niet.

Een eindige automaat die dit modelleert, moet dus het idee implementeren dat je op een gegeven moment bezig bent met een gegeven regel; dat je in die toestand een karakter in kunt lezen; dat dat karakter bij die regel past, aangeeft dat je overgaat naar de volgende regel, of vastloopt. Dit idee valt zeer goed te vangen in een graaf:

  1. Voor iedere toestand van de automaat, bevat de graaf een punt.
  2. Ieder inlezen van een karakter past bij een kant van de graaf.
    1. Een kant tussen punten, is een overgang van de ene toestand naar een andere toestand – en dus van de ene vormregel naar een andere.
    2. Een kant die een lus is, komt overeen met het soort regel dat zegt "nul of meer keer een X inlezen"

Voer daarnaast afspraken in dat je altijd in een vast punt (een vaste toestand) begint, dat niet verder kunnen in bepaalde toestanden in orde is ("accepterende toestanden") en in andere toestanden niet (de automaat "loopt vast") en je hebt een eindige automaat.

Daarnaast heeft het gebruik van een graafmodel het voordeel dat bekende graafalgoritmen kunnen gebruikt worden om de taal te analyseren. Minimale modellen opstellen, bepalen of iedere toestand in het model wel bereikbaar is. Al dat soort dingen behoren tot het "standaardarsenaal" van de grafentheorie. En bovendien, kleine automaten zijn eenvoudig te illustreren door de bijbehorende graaf te tekenen.

Nemen we als voorbeeld de taal T van hierboven en splitsen we de regels verder op. Ieder woord in de taal T is dan te vangen in de volgende reeks vormregeltjes:

  1. begint met 0 of meer keer een a;
  2. dan volgt een c;
  3. dan volgen 0 of meer c's;
  4. dan volgt een a of een b;
  5. dan volgt een a of een b;
  6. dan volgt een a of een b;
  7. dan volgen 0 of meer c's;
  8. dan volgt een a;
  9. dan volgt een b;
  10. dan volgt een c;
  11. dan volgt niets meer.

We kunnen deze taal illustreren met de volgende graaf:

Graaf van de hierboven beschreven reguliere taal

In de bovenstaande graaf zijn de kanten gedecoreerd met de tekens die horen bij die toestandsovergangen. Merk de lussen op die voor "0 of meer keer ..." gebruikt worden. Met een "losse toestandsovergang" (een kant die nergens vandaan komt) is aan de linkerkant aangegeven wat de begintoestand van de automaat is. Met een extra punt is aangegeven wat de accepterende toestand is – komt de automaat bij het lezen van de invoer in deze toestand en is de invoer dan op, dan accepteert de automaat en behoorde de invoer tot onze voorbeeldtaal. Volgt er daarna nog invoer, dan volgt een overgang naar een niet-accepterende toestand waarvandaan geen transities meer zijn; de automaat loopt dan vast in die niet-accepterende toestand en de invoer kan dan niet herkend worden als een woord uit de voorbeeldtaal. Deze regel geldt overigens ook algemeen: als er vanuit een bepaalde toestand geen kant is gedecoreerd met het volgende invoerkarakter, dan zit de automaat vast.

Deterministische eindige automaten[bewerken]

Formeel is een deterministische eindige automaat (DFA) een automaat M = (Q, \Sigma, \delta, q_0, F) met

Q een eindige verzameling toestanden
\Sigma een eindige verzameling symbolen, het alfabet van de automaat (of taal) geheten
\delta een totale functie Q \times \Sigma \rightarrow Q, de transitiefunctie, waarbij de uitkomst opnieuw een toestand is
q_0 \in Q de begintoestand
F \subseteq Q de verzameling accepterende toestanden

Van deze automaat M zeggen we dat hij een taal L(M) accepteert. Deze taal is de verzameling van woorden – rijen symbolen uit het alfabet – waarvoor geldt dat M in een accepterende toestand eindigt bij verwerking van die woorden.

De bovenstaande definitie geeft een machine M die overeenkomt met simpele grafen zoals hierboven geïllustreerd; de toestanden komen overeen met knopen in de graaf, elementen van de transitiefunctie met kanten, het alfabet zijn de symbolen die verwerkt worden, de eindige toestanden uit de verzameling toestanden zijn aangegeven en ook de begintoestand.

De "werking" van de machine wordt beschreven door de transitiefunctie \delta. Deze functie definieert voor iedere toestand en voor iedere mogelijke volgende invoer wat de toestand is waarnaar de automaat overgaat. Voor ieder paar (toestand, symbool) is maar één volgende toestand gedefinieerd – de automaat is deterministisch.

Merk op dat volgens deze definitie, de transitiefunctie een definitie moet geven voor ieder paar van toestand en symbool. Zelfs als vanuit de gegeven toestand een bepaald symbool niet "ingelezen mag worden". Dit is handig bij het modelleren en ook makkelijk bij de wiskunde. Om het tekenen van deterministische automaten makkelijker te maken, worden toestanden waaruit geen eindtoestand kan worden bereikt vaak weggelaten (zoals hierboven ook gebeurd is, in het vorige hoofdstuk).

Iedere deterministische eindige automaat heeft precies één begintoestand. Er mogen echter meerdere accepterende toestanden zijn – sterker nog, het is goed mogelijk een automaat te hebben waarin iedere toestand accepterend is. In het bijzonder komt het regelmatig voor dat de begintoestand accepterend is; in dat geval zit het lege woord in de taal.

Het is niet helemaal duidelijk wie een DFA voor het eerst heeft beschreven, maar doorgaans wordt het artikel van de Amerikanen Warren Sturgis McCulloch en Walter Pitts, "A logical calculus of the ideas imminent in nervous activity" uit 1943 genoemd.

Niet-deterministische eindige automaten[bewerken]

Formeel is een niet-deterministische eindige automaat (NFA) een automaat M = (Q, \Sigma, \delta, q_0, F) met

Q een eindige verzameling toestanden
\Sigma een eindige verzameling symbolen, het alfabet van de automaat (of taal) geheten
\delta een functie Q \times (\Sigma \cup \{\epsilon\}) \rightarrow \wp(Q), de transitiefunctie
I \subseteq Q de verzameling begintoestanden
F \subseteq Q de verzameling accepterende toestanden

Deze automaat lijkt op de DFA die hierboven beschreven is. Er zijn echter enkele verschillen:

  1. De transitiefunctie definieert bij een NFA voor ieder paar (toestand, symbool) een verzameling van vervolgtoestanden. Bij de verwerking van invoer wordt uit deze toestanden een willekeurige toestand gekozen als vervolgtoestand. Dat wil zeggen dat het verloop van de verwerking van invoer niet altijd voorspelbaar is – de machine is niet-deterministisch.
  2. Er is een verzameling begintoestanden waaruit er 1 wordt gekozen als relevante begintoestand bij het controleren van een woord.

Daarnaast zijn er de zogenaamde NFA's met stille overgangen. Vanuit iedere toestand kan de automaat een element van de invoer proberen te verwerken, maar er is bij deze NFA's ook de "stille overgangen" (in de definitie hierboven weergegeven met als symbool \epsilon, waarbij \epsilon al dan niet een element van \Sigma kan zijn) – een soort van "gratis" transitie, waarbij indien dit zo gedefinieerd werd in de transitiefunctie van 1 bepaalde toestand naar een andere kan worden overgesprongen zonder invoer. Een dergelijke transitie komt overeen met het idee dat een rij symbolen hetzelfde is als diezelfde rij symbolen met een aantal "lege karakters" tussengevoegd:

abcabcabc = abc \epsilon abc \epsilon \epsilon \epsilon a \epsilon bc

Ook de aanwezigheid van lege karakters maakt een automaat niet-deterministisch, omdat in een toestand de keuze kan bestaan tussen het verwerken van een invoerkarakter of overgaan naar de volgende toestand via een \epsilon-transitie.

Van deze automaat M zeggen we dat hij een taal L(M) accepteert. Deze taal is de verzameling van woorden w – rijen symbolen uit het alfabet \Sigma – waarvoor geldt

\delta^*(q_0, w) \cap F \neq \emptyset

waarbij  q_0 \in I, dit wil zeggen dat ten minste één van de toestanden die bereikt kan worden door w in te geven een eindtoestand is.

NFA's zijn voor het eerst beschreven door Michael Rabin en Dana Scott in hun gezamenlijke artikel "Finite Automata and Their Decision Problem" dat gepubliceerd werd in 1959.

Gelijkwaardigheid van DFA's en NFA's[bewerken]

Er doet zich nu de vraag voor welke soort automaat de meeste uitdrukkingskracht heeft. Welke automaat – DFA of NFA – accepteert de grootste verzameling talen?

Een DFA is deterministisch, makkelijker te besturen en plannen dan een NFA. Maar een NFA heeft meer soorten transities en kan zelfs meerdere vervolgtoestanden definiëren per toestand en invoerkarakter. Daar staat tegenover – een NFA kan misschien een keuze maken voor een vervolgtoestand die resulteert in een vastloper, zelfs als de invoer wel tot de taal van de automaat behoort.

Welke is nu sterker als model? Het antwoord is opvallend: geen van beide. Voor iedere NFA bestaat een gelijkwaardige DFA, voor iedere DFA tenminste een gelijkwaardige NFA.

Om te beginnen met het laatste: voor iedere DFA bestaat tenminste een gelijkwaardige NFA. Het bewijs van deze stelling is triviaal. Volgens de definitie heeft een DFA voor elk paar van toestand en alfabetteken precies één opvolgertoestand, terwijl een NFA voor elk paar een willekeurig aantal opvolgertoestanden kan hebben. Dat betekent dat elke DFA al een speciaal soort NFA is, omdat 'willekeurig' ook 1 kan zijn.

Bovendien kan elke NFA in een gelijkwaardige DFA omgezet worden. Of formeel gesteld: Zij M_N = (Q_N, \Sigma_N, \delta_N, q_0, F_N) een NFA. Dan bestaat er een DFA M_D = (Q_D, \Sigma_D, \delta_D, \{q_0\}, F_D) met L(M_D) = L(M_N). Deze DFA valt te construeren uit M_N door middel van het volgende algoritme, dat bekend staat onder de naam subset-constructie:

  1. Begin een nieuwe graaf met als enige knoop \{q_0\}.
  2. Herhaal de volgende stappen, totdat er voor iedere knoop van de graaf een uitgaande kant is voor ieder element van het alfabet:
    1. Neem een knoop \{q_i, q_j, \ldots, q_k\} die voor één of andere a \in \Sigma geen uitgaande kant heeft.
    2. Bereken voor q_i, q_j, \ldots, q_k in de NFA de verzameling toestanden die te bereiken zijn via transitie-overgangen met a – dat zijn dus de directe overgangen, de \epsilon-transities vanuit q_i, q_j, \ldots, q_k en de \epsilon-transities vanuit de eerder genoemde directe overgangen.
    3. Zij q_l, q_m, \ldots, q_n de verzameling van alle toestanden die in de vorige stap gevonden zijn.
    4. Als de knoop \{q_l, q_m, \ldots, q_n\} nog niet bestaat in de nieuwe graaf, voeg hem dan toe.
    5. Voeg een kant toe in de nieuwe graaf van \{q_i, q_j, \ldots, q_k\} naar \{q_l, q_m, \ldots, q_n\} gelabeld a.
  3. Stel de verzameling F_D samen: dit is de verzameling knopen in de nieuwe graaf die een q_i bevatten uit de NFA met q_i \in F_N.
  4. Als M_N het lege woord accepteert (q_0 is accepterend of een \epsilon-transitie vanuit q_0 leidt tot een accepterende toestand), maak dan \{q_0\} accepterend.

Bewijs van het bovenstaande algoritme:

  1. Als het algoritme klopt, dan bestaat er voor iedere NFA een equivalente DFA. We concentreren dus verder alleen op het algoritme.
  2. Het algoritme is eindig; het kan nooit eeuwig doorlopen en dus geen antwoord geven. Dit valt als volgt in te zien:
    1. Stappen 1, 3 en 4 zijn triviaal eindig.
    2. Iedere herhaling van stap 2 voegt een kant toe aan de nieuwe kant van de nieuwe graaf (dus de DFA). Maar het aantal knopen van de NFA is eindig. En het aantal knopen van de DFA kan hoogstens de machtsverzameling zijn van de verzameling knopen van de NFA. En het maximaal aantal kanten van de DFA is dus 2^{|Q_N|} |\Sigma|. Dat is eindig, dus het maximaal aantal herhalingen van stap 2 is ook eindig.
  3. De correctheid van het algoritme volgt uit inductie naar de lengte van de invoer van de automaat:
    1. Basisgeval, invoerlengte = 0: Als de NFA het lege woord accepteert, dan is q_0 accepterend (of een toestand bereikbaar uit q_0 via \epsilon-transities). Dan is in de DFA \{q_0\} accepterend en accepteert de DFA het lege woord. Accepteert de NFA het lege woord niet, dan is \{q_0\} niet accepterend en loopt de DFA vast op het lege woord.
    2. Hypothese, invoerlengte is n: Als een invoer v ter lengte n de NFA in een toestand q_i brengt, dan is er in de DFA een toestand Q_i = \{\ldots, q_i, \ldots\} waarin de DFA terecht komt bij invoer v.
    3. Stap, invoer = va, invoerlengte = n + 1: Door verwerking van de eerste n karakters van de invoer (het gedeelte v) door de DFA, komen we in toestand Q_i vanuit toestand \{q_0\}, zoals volgt uit de hypothese. In de NFA komen we in een toestand q_i, vanuit q_0. Komen we vervolgens door verwerking van a in de NFA in toestand q_j vanuit q_i. Volgens de constructie van stap 2 van het algoritme, moet er in de DFA nu een transitie zijn vanuit toestand Q_i naar Q_j = \{\ldots, q_j, \ldots\} met label a. En dus kan de DFA vanuit \{q_0\} in toestand Q_j komen. Bovendien geldt dat als q_j accepterend is in de NFA, dat Q_j accepterend is in de DFA.

Overige opmerkingen[bewerken]

Er zijn verschillende computertalen gedefinieerd om op vlotte wijze eindige automaten te implementeren. W3C ontwikkelde SCXML, State Chart XML. Eindige automaten blijken een specifiek geval van een zogeheten Petrinet te zijn. DFA's en NFA's kunnen op elk moment slechts in 1 toestand verkeren. Met Petrinets kunnen daarnaast meertoestandssituaties worden beschreven.

Reguliere grammatica's, eindigetoestandsautomaten en reguliere expressies genereren in de Chomskyhiërarchie de reguliere talen en zijn hierdoor equivalent.

Bronnen, noten en/of referenties
  • (en) Peter Linz, An introduction to formal languages and automata, D. C. Heath and Company, 1996, ISBN 0-669-35403-1
  • (de) Uwe Schöning, Theoretische Informatik — kurz gefasst, 5. Auflage, Spektrum, 2008, ISBN 978-3-8274-1824-1
  • (en) Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997, ISBN 0-534-94728-X
  • (en) John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd Edition. Pearson Addison-Wesley Computing, 2007, ISBN 0-321-45536-3