Eindigetoestandsautomaat

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

Een eindigetoestandsautomaat is een model voor het gedrag voor een systeem, bestaande uit een eindig aantal toestanden, overgangen tussen die toestanden en acties. Eindigetoestandsautomaten worden 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.

Binnen de eindigetoestandsautomaten onderscheiden we twee soorten van automaten, de deterministische eindige automaten (DFA, van het Engelse deterministic finite automaton), en de niet-deterministische eindige automaten (NFA). Deze automaten zijn aan verschillende regels onderworpen, maar beschrijven dezelfde klasse van talen.

Eindige automaten en reguliere talen[bewerken]

Herkenning[bewerken]

Zoals bij ieder model van berekenbaarheid (zoals de Turingmachine) wordt ook de werking van een automaat 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 karakters kan inlezen en dan de vraag kan beantwoorden of die rij karakters 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.

Reguliere talen[bewerken]

Eindige automaten herkennen een klasse van talen die bekendstaat als de klasse der reguliere talen. Dit zijn talen die vrij simpel zijn qua structuur. 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 karakters) 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 tenslotte 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 gemodelleerd als grafen. De reden hiervoor is dat een graaf zo mooi past bij de manier waarop een reguliere taal werkt.

Een reguliere taal bestaat eigenlijk simpelweg uit een opsomming van vormregeltjes die afgewerkt moeten worden. Kan een woord verwerkt worden met behulp van die regeltjes (of gevormd worden met behulp van die regeltjes), dan behoort het woord tot de taal. Anders niet.

Een eindige automaat die dit moet modelleren, moet dus het idee modelleren 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 simpele 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 toestand naar toestand – van de ene regel naar de volgende.
    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 een graafmodel het voordeel dat je zeer veel, bekende graafalgoritmen kunt gebruiken om je taal te analyseren. Minimale modellen opstellen, bepalen of iedere toestand in je model wel bereikbaar is, al dat soort dingen behoren tot het "standaardarsenaal" van de grafentheorie. En bovendien, voor kleinere automaten kun je ook makkelijk illustreren – door een graaf uit te tekenen.

Nemen we als voorbeeld de taal van hierboven en splitsen we de regels iets uit:

Ieder woord in de taal

  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 nu de taal vangen in en illustreren met de volgende graaf:

Graaf ter illustratie 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 met

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.

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 toestandsfunctie
I \subseteq Q de verzameling begintoestanden
F \subseteq Q de verzameling accepterende toestanden

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

  1. De toestandsfunctie 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 mag gekozen worden als begintoestand bij het lezen 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 toestandsfunctie van 1 bepaalde toestand naar een andere kan overgesprongen worden 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

Uiteraard maakt de aanwezigheid van lege karakters een automaat ook 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.

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

Uiteraard 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: geen van beide. Voor iedere NFA bestaat een gelijkwaardige DFA, voor iedere DFA ten minste een gelijkwaardige NFA.

Om te beginnen met het laatste: voor iedere DFA bestaat ten minste 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 een voor elk paar een willekeurig aantal opvolgertoestanden kan hebben. Dat betekent dat elke DFA eigenlijk al een speciaal soort NFA is.

Ook kunnen we elke NFA in een DFA omzetten. 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 de volgende procedure:

  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 de stelling:
  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 toe aan de nieuwe graaf. 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.
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