Eindige toestandsautomaat

Een eindige toestandsautomaat is een model van berekenbaarheid in de wiskunde en informatica. Eindige toestandsautomaten zijn gebaseerd op grafen en beschrijven een klasse van formele talen die de reguliere talen heten.

Binnen de eindige toestandsautomaten onderscheiden we twee soorten van automaten, de deterministische eindige automaten (en: Deterministic Finite Automaton – DFA) en de non-deterministische eindige automaten (en: Non-deterministic Finite Automaton – NFA). Deze automaten zijn aan verschillende regels onderworpen, maar beschrijven precies dezelfde klasse van talen.

Inhoud

1 Eindige automaten en reguliere talen
2 Deterministische eindige automaten
3 Non-deterministische eindige automaten
4 Gelijkwaardigheid van DFA's en NFA's
5 Voor iedere, reguliere taal bestaat een DFA
6 Bronnen

[bewerk] Eindige automaten en reguliere talen

[bewerk] Herkenning

Zoals bij ieder model van berekenbaarheid (zoals de Turingmachine) wordt de werking van een automaat uitgelegd in termen van het herkennen van een bepaalde, formele taal. Een formele taal T is 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 in kan lezen en dan de "ja/nee-vraag" kan beantwoorden of die rij karakters een woord is uit T of niet. "Ja" staat hierbij voor herkenning, "nee" voor geen herkenning, weigering, of welke terminologie men hiervoor ook wenst te gebruiken.

[bewerk] Reguliere talen

Eindige automaten herkennen een klasse van talen die bekend staat 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. Bijvoorbeeld:

Zij T een reguliere taal, met als alfabet (= verzameling toegestane karakters) de verzameling

{a, b, c}

Dan is de taal T die verzameling van woorden die gevormd worden door:

eerst 0 of meer keer een a

dan tenminste éé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 uit de taal T zijn dan aaaaaccabacabc, aacaaaabc, cbbbabc, aaccccccccccccccbabccabc en acaaacabc.

Daarentegen hoort de rij bcbaa niet in T thuis. Evenmin als aaaacaaaccab, ccde of aaaaaaabc.

[bewerk] Eindige automaten en grafen

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:

Voor iedere toestand van de automaat, bevat de graaf een punt.
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

begint met 0 of meer keer een a;
dan volgt een c;
dan volgen 0 of meer c's;
dan volgt een a of een b;
dan volgt een a of een b;
dan volgt een a of een b;
dan volgen 0 of meer c's;
dan volgt een a;
dan volgt een b;
dan volgt een c;
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.

[bewerk] Deterministische eindige automaten

Formeel is een deterministische eindige automaat (DFA) een automaat $M$ met

M = (Q,Σ,δ, q 0, F)

met

Q

een eindige verzameling toestanden

Σ

een eindige verzameling symbolen, het alfabet van de automaat (of taal) geheten

δ

een totale functie $Q \times \Sigma \rightarrow Q$ , de transitiefunctie

$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 $δ$ . 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 (toestand, 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, maar bij het uittekenen van de graaf van een machine betekent het dat je vaak en veel nutteloze toestanden krijgt – toestanden die er alleen maar zijn om de machine in vast te laten lopen. Daarom worden dit soort loze transities en toestanden bij een illustratie meestal weggelaten (zoals hierboven ook gebeurd is, in het vorige hoofdstuk).

Ieder automaat heeft maar éé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.

[bewerk] Non-deterministische eindige automaten

Formeel is een non-deterministische eindige automaat (NFA) een automaat $M$ met

M = (Q,Σ,δ, q 0, F)

met

Q

een eindige verzameling toestanden

Σ

een eindige verzameling symbolen, het alfabet van de automaat (of taal) geheten

δ

een functie $Q \times (\Sigma \cup \{\epsilon\}) \rightarrow \wp(Q)$ , de transitiefunctie

$q_0 \in Q$ de begintoestand

$F \subseteq Q$ de verzameling accepterende toestanden

Deze automaat lijkt heel erg op de DFA die hierboven beschreven is. Het enige verschil zit in de definitie van de transitiefunctie.

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 non-deterministisch.

Daarnaast kent de NFA nog een extra soort transitie. Vanuit iedere toestand kan de automaat een element van de invoer proberen te verwerken, maar er is bij een NFA ook de "lege transitie" (in de definitie hierboven weergegeven met als symbool $ε$ , waarbij $\epsilon \not\in \Sigma$ ) – een soort van "gratis" transitie, waarbij geen element van de invoer verwerkt wordt. Een dergelijke transitie komt overeen met het idee dat een rij symbolen hetzelfde is als diezelfde rij symbolen met een aantal "lege karakters" tussengevoegd:

a b c a b c a b c = a b c ε a b c εεε a ε b c

Uiteraard maakt de aanwezigheid van lege karakters een automaat ook non-deterministisch, omdat in een toestand de keuze kan bestaan tussen het verwerken van een invoerkarakter of overgaan naar de volgende toestand via een $ε$ -transitie.

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

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 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: neem een DFA, knip hem in twee stukken. Voeg vervolgens een extra toestand toe. Verbind het eerste stuk van de DFA met de nieuwe toestand middels een $ε$ -transitie. Verbind de nieuwe toestand met het tweede stuk van de DFA middels een $ε$ -transitie. Nu heb je een NFA gelijkwaardig met de oorspronkelijke DFA.

De andere kant op is lastiger. Toch valt het aan te tonen:

Zij

M N = (Q N,Σ N,δ N, q 0, F N)

een NFA. Dan bestaat er een DFA

M D = (Q D,Σ D,δ D,{q 0}, F D)

met

L (M D) = L (M N)

. Deze DFA valt te construeren uit

M N

middels de volgende procedure:

Begin een nieuwe graaf met als enige knoop ${q 0}$ .
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 middels transitie-overgangen met $a$ – dat zijn dus de directe overgangen, de $ε$ -transities vanuit $q_i, q_j, \ldots, q_k$ en de $ε$ -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$ .
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$ .
Als $M N$ het lege woord accepteert ( $q 0$ is accepterend of een $ε$ -transitie vanuit $q 0$ leidt tot een accepterende toestand), maak dan ${q 0}$ accepterend.

Bewijs van de stelling:

Als het algoritme klopt, dan bestaat er voor iedere NFA een equivalente DFA. We concentreren dus verder alleen op het algoritme.
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.
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 $ε$ -transities</math>). 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.