We kennen natuurlijke talen zoals het Nederlands maar we kennen ook programmeertalen zoals JavaScript. Een formele taal heeft een veel eenvoudigere structuur dan een natuurlijke taal en is daarom makkelijker te automatiseren.
We bestuderen in deze module de theorie van formele talen en de daarbij behorende automaten en grammatica. Het bestuderen is een onderdeel van Computational Thinking en helpt je om je eigen denkniveau naar een hoger level te krijgen. Een strategie die vaak wordt toegepast is het opsplitsen van een groter probleem in kleinere stukjes.
De automaten die wij gaan bestuderen zijn voorlopers van de Turing machine ontwikkeld door de wiskundige Alan M. Turing. De Turing machine is een mechanisme dat symbolen manipuleert en men kan hiermee de logica van elke mogelijke computer simuleren. Het is al in 1936 bedacht.
Een formele taal kan op drie manieren worden weergegeven:
In de vorm van een grammatica. Een grammatica zijn de regels van de taal zoals bijvoorbeeld de lengte van een zin of hoe de zin moet worden samengesteld.
In de vorm van een automaat. Een automaat is een graaf die bedoeld is om te checken of een bepaalde zin of woord wordt geaccepteerd.
In de vorm van een reguliere expressie. Een reguliere expressie geeft een beschrijving van een taal. De expressie a* geeft aan dat er 0 of meer a's in de zin zitten.
Wat is een taal?
Het woord taal kan verschillende betekenissen hebben. In het algemeen zou je kunnen zeggen dat taal een systeem is om ideeën, feiten of concepten uit te drukken. Iedere taal heeft een verzameling symbolen zoals het alfabet. Ook heeft een taal regels om met die symbolen te werken zoals de Nederlandse grammatica.
Er zijn twee soorten talen:
Natuurlijke talen: Dit zijn talen die in de loop van de tijd zijn ontstaan zoals bijvoorbeeld het Engels.
Formele talen: Dit zijn kunstmatige talen. Een programmeertaal is altijd een kunstmatige taal. Esperanto is ook een kunstmatige taal.
Een taal kan worden geformuleerd als een zekere hoeveelheid strings die zijn geformeerd met karakters uit een zekere verzameling. Het Nederlands is opgebouwd uit strings (woorden) die zijn gevormd uit de verzameling van het alfabet. Uit deze woorden kunnen een bijna oneindige hoeveelheid zinnen worden gevormd.
Een taal is dus vaak een verzameling woorden, gevormd met karakers uit een alfabet. Een verzameling van een taal duiden we aan met het L teken. Een verzameling karakters duiden we aan met ∑ (sigma). De verzameling van de woorden van de taal Nederlands is L={a,b.....z, A....Z}. Dit geldt ook voor de taal Engels. De talen Nederlands en Engels hebben dus hetzelfde alfabet of dezelfde verzameling maar vormen met die verzameling karakters verschillende woorden waardoor er een verschillende taal ontstaat. Een verzameling is dus niet hetzelfde als een taal.
Het lambda symbool
Stel dat we uitgaan van het volgende alfabet:
∑ = {a,b}
We kunnen dan alle strings (woorden) definiëren als
L = {a,b,aa,ab,ba,bb,aaa,aaab.....}. De woorden van deze taal zijn echter niet compleet. We kunnen namelijk ook een lege string produceren. Dat schrijven we met het teken λ. Dit is het zogenaamde lambda-teken (spreek uit: labda).
De complete verzameling is dus L = {λ, a,b,aa,ab,ba,bb,aaa,aaab.....}
Je ziet dus dat bij een taal ook altijd een lege string hoort (tenzij we dat anders aangeven). Er valt ons nog iets op. De bovenstaande verzameling L eindigt met .... Dit geeft aan dat de taal oneindig is. We kunnen dus een oneindig aantal woorden maken. Oneindige talen zijn vaak niet interessant.
De Kleene ster
Hierboven hebben we de gehele bovenstaande taal aangegeven met L = {λ,a,b,aa,ab,ba,bb,aaa,aaab.....}.. Dit kan ook anders namelijk met ∑*. De ster noemen we de Kleene closure. We kunnen bijvoorbeeld zeggen dat L1= {a,b,ab,ba} en L0= {λ}. ∑* is dan L0 ∪ L1 en is dus de verzameling {λ,a,b,ab,ba}. ∑* is de vereniging van de talen L0 en L1.
We kunnen de hele taal ook zonder lambda aangeven. Dit duiden we aan met ∑+.
Dus ∑+=∑* - {λ}.
De inverse, de lengte en de formele schrijfwijze
De lengte van een string geven we aan met |w| waarbij het symbool w een variable is die de string bevat. Dus als w 2 karakters heeft dan schrijven we |w|=2.
Stel dat we een taal construeren met ∑={a,b} en L={aa,bb} waarbij geldt dat |w| ≤ 2. De inverse van de taal L is dan L'={λ,a,b,ab,ba}, dit zij alle mogelijke woorden die niet in L zitten inclusief λ. We noemen L' de inverse van de taal L.
L ∪ L' = {λ,a,b,ab,ba,aa,bb} met |w| ≤ 2 is alles bij elkaar. Het ∪ betekent de vereniging van en is dus niets anders dan de twee verzamelingen bij elkaar voegen.
Voor L ∪ L' met |w| ≤ 2 is ook een formele schrijfwijze:
L={w∈{a,b}* : |w| ≤ 2}
Hier staat: de taal L bevat woorden waarvoor we de variable w gebruiken. w kan alle combinaties met a en b bevatten waarbij de lengte van w kleiner of gelijk moet zijn dan 2.
Grammatica
Om talen binnen de informatica te kunnen te bestuderen hebben we een systeem nodig om ze te kunnen beschrijven. We hebben al een formele schrijfwijze maar deze is beperkt. We hebben een complexer systeem nodig.
In een grammatica kun je het volgende onderscheiden:
Productieregels zijn regels om een zin te maken en vormen het hart van de grammatica. We duiden dit aan met een P
Het startsymbool of hoofdsymbool. We duiden dit aan met een S
De hulpsymbolen: We duiden dit aan met V van variable. Het is dus alles wat geen eindsymbool is.
Als laatste zijn er de eindsymbolen. We duiden dit aan met een T (terminals).
Nu hebben we een grammatica die we als volgt kunnen definiëren: G={V,T,S,P}
Productieregels van een formele taal
Stel dat we van een formele taal zeggen dat de volgende regel de productieregel is:
S → y
Hier staat: in plaats van S mag je ook y schrijven.
S (het startsymbool) is een element van V (alle hulpsymbolen) en y is een element van T.
Stel nu dat we een string willen maken met de vorm ab. Dan schrijven we het volgende:
We beginnen met een hulpsymbool S.
S →
Deze laten we verwijzen naar een a, dus in de plaats van S schrijven we een a.
S → a
Nu moeten we nog een b produceren. Dat zouden we als volgt kunnen doen met het hulpsymbool B en het eindsymbool b:
S → aB
B → b
Als we hier nu een afleiding van maken krijgen we de string ab.
Dus: S => aB => ab
Een stapje verder
We gaan nu een stapje verder. We definiëren een grammatica als volgt:
G=({S},{a,b},S,P)
Dus {a,b} zijn de eindsymbolen
De productieregels P zijn:
S → aSb
S → λ
Je mag dus nu kiezen. S kan zowel aSb worden of de lege string. Als je kiest voor de eerste regel komen we een fenomeen tegen wat we recursie noemen.
S⇒aSb⇒aaSbb⇒aabb.
Bij de laatste afleiding hebben we gekozen om de eerste productieregel twee keer toe te passen maar we hadden oneindig door kunnen gaan.
De productieregels kunnen we ook anders opschrijven in de vorm van een grammatica:
L(G)={anbn : n ≥ 0}
Hier staat:
De taal L met gramatica G bevat de woorden gevormd met een alfabet bestaande uit de karakters a en b waarbij we n keer een a samenvoegen met n keer een b . Hierbij moet n groter of gelijk zijn aan 0.
Let er nu op dat er geen komma staat tussen a en b. Deze eindsymbolen worden nu aan elkaar geschreven. Daardoor is een afleiding die leidt tot ba niet mogelijk.
Andersom redeneren
Ingewikkelder wordt het wanneer je van een formele beschrijving van een taal de productieregels moet geven. Neem de volgende taal:
L={anbm : n ≥ 0, m > n}
Hoe ontwikkel je hier nu productieregels van? Laten we beginnen met de taal informeel te omschrijven. Er kunnen 0 of meer a-strings worden geformeerd en er is altijd één b meer dan een a. Hieruit kun je concluderen dat er minimaal één b moet zijn.
Een regel zou dan kunnen zijn:
S → aSb | b
S → λ
Kun je zien wat hier fout aan is? Je kunt nu in één keer kiezen voor een lege string waardoor n=0 en m=0 en dat voldoet niet aan de formele beschrijving.
Je moet dus productieregels maken waarbij je minimaal één b hebt. Dan zou je het zo kunnen doen.
S → AB
A → aAb | λ
B → Bb | b
JFlap
JFlap is tool wat ons helpt om een automaat te maken en uit te proberen. JFlap is hier te downloaden. JFlap heeft geen rechten nodig, alleen Java. Je kunt JFlap starten door dubbel te klikken op JFLAP8_beta.jar. Mocht Jflap het niet doen, dan even opnieuw Java installeren (oude versie eerst deïnstalleren).
Je kunt JFlap op diverse manieren grammatica's testen. We zullen een voorbeeld geven van onderdeel 1.8 waarin we een grammatica hebben gemaakt. Klik in JFlap op Grammar.
Je bent nu in staat om een grammatica in te voeren en te testen. De grammatica:
S → AB
A → aAb | λ
B → Bb | b
Deze kun je invoeren door te dubbelklikken op de invoervakjes. De pipe (|) gebruik je niet maar je voert een apart veld in.
Onderin zie je tevens de grammatica verschijnen inclusief de hulpsymbolen.
Nu kun je testen welke strings deze grammatica accepteert. Dit kun je testen door te klikken op Brute Force Parse.
Vervolgens kun je testen welke strings de automaat accepteert door deze achter de input in te voeren en vervolgens te klikken op SET.
Als je daarna klikt op Complete kun je zien of een string wordt geaccepteerd. In bovenstaand geval is dat niet zo (Input recected!).
De onderstaande antwoorden moet je zelf nakijken; vergelijk jouw antwoorden met de goede
antwoorden, en geef aan in welke mate jouw antwoorden correct zijn.
Verklarende lijst van gebruikte symbolen en afkortingen
Symbool
Uitspraak
Omschrijving
∑
sigma
Een alphabet
L
Een taal
L'
L accent
De inverse van de taal L, alles wat niet in L zit.
λ
labda
Een lege string
∪
union
Operator om twee verzamelingen samen te voegen
∈
element van
Is een element van; Voorbeeld: w∈{a,b} w kan nu aa of bb zijn
⊆
deelverzameling van
Is een deelverzameling van
G
Een grammatica
S
Startsymbool, deze variable bevat het resultaat en is altijd onderdeel van V
V
Hulpsymbolen, de verzameling met alle gebruikte variablen
T
Eindsymbolen, de verzameling met het te gebruiken alfabet
P
De productieregels
{ }
Een verzameling
|w|
De lengte van variabele w. Als w={ab} betekent dat |w|=2
|
pipe
Of; S → a | b betekend dat S of a of b kan bevatten
∑*
sigma ster
De verzameling van alle woorden te maken met Σ inclusief een lege string
∑+
sigma plus
De verzameling van alle woorden te maken met Σ inclusief zonder lege string
{a,b}
Een verzameling van een losse a en een losse b
{ab}
Een verzameling met alleen het woord ab (geen komma)
Een aantal regels:
∑* = L ∪ L'
∑+ = ∑* - λ
|λ| = 0
G={V,T,S,P}
Samenvatting talen
∑ is een alfabet, hierin staan alle mogelijke symbolen bijv.
∑ = {a,b,c}
λ is null oftewel leeg, het bevat niets.
L is een taal met woorden bijvoorbeeld met het alfabet hierboven:
L is een verzameling van woorden {}
L={a,b,c,aa,ab,ac,bb,ba,bc,cc,ca,cb,aaa,aab,...}
De taal L met een lege string:
L={λ,a,b,c,aa,ab,ac,bb,ba,bc,cc,ca,cb,aaa,aab,...}
De kleene ster geeft een verzameling woorden aan inclusief een lege string λ
∑*
is dus hetzelfde als:
L={λ,a,b,c,aa,ab,ac,bb,ba,bc,cc,ca,cb,aaa,aab,...}
Sigma + geeft dezelfde verzameling maar dan zonder de lege string λ
∑+
oftwel:
L={a,b,c,aa,ab,ac,bb,ba,bc,cc,ca,cb,aaa,aab,...}
Je kunt dan ook zeggen dat:
∑+=∑* - {λ}
of
∑*=∑+ + {λ}
De maximale lengte van een woord kunnen we aangeven met |w| waarbij w de variable is waat het woord in komt.
Bijvoorbeeld:
|w|≤2
Geeft een maximale woordlengte van 2, met een ∑={a,b} geeft dat de taal:
L = {λ,a,b,aa,bb,ab,ba}
λ doet mee omdat de lengte 0 ook kleiner is dan 2
De inverse van een taal L' bevat alle woorden die niet in de taal L voorkomen.
Stel dat we een ∑={a,b} met de gegeven taal L={aa,bb} dan is de de inverse van de taal L':
L'={λ,a,b,ab,ba}
Als we de twee verzamelingen bij elkaar optellen L ∪ L' dan krijgen we weer alle mogelijke woorden ∑*
Het vorige voorbeeld kunnen we ook formeel opschrijven:
L={w∈{a,b}* : |w| ≤ 2}
Hier staat:
De taal L is een verzameling van woorden waarbij ieder woord w bestaat uit alle combinaties van het alfabet {a,b} waarbij de lengte van het woord w maximaal 2 is.
Bij een taal hoort ook een gramatica, je mag niet zomaar alle combinaties van letters maken in een taal.
Een gramatica is als volgt opgebouwd:
G={V,T,S,P}
Waarbij:
V zijn hulpsymbolen oftwel variablen altijd geschreven in een hoofdletter
T zijn de eindsymbolen altijd geschreven in een kleine letters
S is het startsymbool de eerste variable altijd geschreven in een hoofdletter
P zijn de regels die bij de gramatica horen
Voorbeelden:
S → y
De uitkomst is {y}
S → a
De uitkomst is {a}
S → aB
B → b
De uitkomst is {ab}
S → aSb
S → λ
De uitkomst is {λ,ab,aabb,aaabbb,...}
Of anders geschreven:
L(G)={anbn : n ≥ 0}
S → AB
A → aAb | λ
B → Bb | b
De uitkomst is {b,abbb,abbbbbbbb,aabbbbb,...}
Automaten 1
Wat is een automaat
Een automaat is een abstract model van een digitale computer of een bepaald systeem. Een computer of automaat heeft essentiële functies. De automaat heeft een mechanisme om input te kunnen lezen. In vroeger tijden was dat bij een computer bijvoorbeeld de invoer van ponskaarten. Vertaald naar een automaat houdt dit in dat de automaat kennis moet hebben over het gegeven alfabet. In het geval van de ponskaarten moet de computer de positie van de gaatjes kunnen lezen en weten wat deze betekenen.
Een ponskaart om de deur van een hotel te openen.
Een computer kan altijd maar één symbool tegelijk lezen en meestal wordt van links naar rechts gelezen. Er dient ook een mechanisme te zijn wat het einde van de string detecteert.
Een automaat produceert ook een output in één of andere vorm. Er kan ook sprake zijn van een tijdelijke opslag.
Soorten automaten
Een automaat kan dus worden gezien als een mechanisme wat strings kan herkennen. Een ander woord voor automaat is accepter. We zullen in de lesonderdelen hierna eindige automaat bestuderen. Dit is een automaat waar een string ingevoerd kan worden en dit leidt tot een eindtoestand. Een eindige automaat heeft altijd een aantal interne toestanden waaronder een begintoetsand. De begintoestand is de toestand waarin de automaat zich bevindt als er nog geen strings zijn ingevoerd.
Een automaat kan non-deterministisch of deterministisch zijn. Deterministisch houdt in dat een ingevoerde string maar op één manier kan worden gelezen. Het is gebruikelijk om deze twee automaten als een afkorting op te schrijven:
een deterministische eindige automaat korten we af met dfa, van het Engelse deterministic finite automaton.
een niet-deterministische eindige automaat korten we af met nfa, van het Engelse nondeterministic finite automaton.
Een automaat voor toegangscontrole
Een automaat met JFlap
We zullen nu eerst via JFlap een eindige automaat maken. Open de tool en klik op Finite Automaton.
In het scherm hierna gaan we een eindige automaat maken in de vorm van een graaf. De grafentheorie is een tak van wiskunde die de eigenschappen van grafen bestudeert. Een graaf bestaat uit punten, deze worden knopen genoemd, die vaak zijn verbonden door lijnen. Als de lijnen pijlen worden dan spreken we van een gerichte graaf.
Maak drie toestanden (dit zijn dus de knopen van de graaf) q0, q1 en q2 met de State Creator.
Maak overgangen (pijlen) met behulp van de Transition Creator.
Uiteindelijk maak je alle overgangen als volgt:
Als je een foutje maakt kun je met de Deleter of met Ctrl-Z het foutje ongedaan maken.
We hebben nu nog een begin- en eindtoestand nodig. Deze kun je maken door met de rechtermuisknop op een toestand te klikken.
Uiteindelijk ziet de volledige automaat er zo uit:
Wat heb je nu gemaakt? Een automaat die strings met 0-en en 1-en accepteert. We zullen dit demonstreren. Klik in het menu Input op Step with Closure..
Stel we hebben de volgende string: 10111. De automaat start in de begintoestand.
Vervolgens leest de automaat het eerste karakter: 1. De automaat komt in de toestand q1 vanwege de overgang die een 1 accepteert.
Bij het lezen van het 2e karakter, 0, komt de automaat weer terug in q0.
Bij het lezen van het derde karakter, een 1, komt de automaat opnieuw toestand q1. De laatste 2 karakters, twee keer een 1, brengt de automaat achtereenvolgens in toestand q2 en opnieuw weer in q1.
Je ziet dat de string wordt geaccepteerd omdat de automaat in q1 komt, de eindtoestand.
Met JFlap strings controleren in een automaat
In de opdracht van het vorige lesonderdeel moest je controleren of de automaat een bepaalde string accepteert. Dit kun je ook laten checken door JFlap. Als je de automaat hebt gemaakt kun je een string invoeren. Klik hiervoor onder input op Step with Closure.
In het navolgende veldje kun je de string invoeren.
Vervolgens kun je met de Step de string laten inlezen. Als de eindtoestand wordt bereikt, is de string geaccepteerd. Het veld van de ingevoerde string kleurt rood als deze niet wordt geaccepteerd.
Een formele definitie voor een automaat.
We zijn nu ook in staat om een definitie te maken voor een automaat.
Q is een eindig aantal sets van interne toestanden.
∑ is een verzameling van de input karakters. We noemen dit het invoeralfabet (input alphabet).
δ (delta) staat voor alle overgangsfuncties (transition function).
q0 is de begintoestand (initial state).
F is de verzameling eindtoestanden (final states) en is dus een deelverzameling van Q. F kan gelijk zijn aan Q. Wiskundig schrijven we dat zo op: F ⊆ Q.
We kunnen nu de volledige automaat geven en geven deze de letter M.
M = {Q, ∑, δ, q0, F }
In JFlap heb je deze definitie misschien ook al gezien. q0 wordt daarin aangegeven met een S.
Een trap state
We zullen proberen de volgende grammatica uit te werken:
L={anb : n ≥ 0}
Deze grammatica produceert strings zoals ab, aab, aaab of b (n=0). Hoe kunnen we een automaat maken die deze strings, en alleen deze strings, accepteert?
We moeten in ieder geval een overgang maken die een oneindige hoeveelheid a-karakters kan lezen. Dat kan als volgt:
Deze automaat kan zowel een lege string als een oneindige hoeveelheid a-karakters. Merk op dat de begintoestand ook tevens de eindtoestand is.
We moeten nu echter ook de b kunnen lezen. Dit kan zo:
Waarbij we q1 als eindtoestand hebben ingesteld.
Je zou nu zeggen dat we klaar zijn maar als we de string aabb invoeren loopt de automaat in feite vast. Tot aab gaat het goed maar de b erna kan de automaat niet meer lezen. Hiervoor moeten we iets extra's maken en dat noemen we een trap state. Elke a of b die erna volgt moet ook kunnen leiden tot een toestand. We gaan deze leiden naar q2. De graaf die dan ontstaat ziet er als volgt uit:
En is het mogelijk om elke string te lezen zonder dat de automaat vast loopt. We noemen dit een totale functie. Als we dus vragen om een totale automaat dan dien je ook rekening te houden met strings die geproduceerd kunnen worden die niet worden geaccepteerd maar die de automaat wel kan lezen.
Substrings herkennen
Een substring is een onderdeel van een string. In de string aabbab is "bab" een substring. Hoe kunnen we een automaat maken die de substring "bab" herkent? Door telkens een deel van de string te lezen en daarna weer terug te gaan naar de begintoestand. Als de substring wel wordt gelezen gaat de automaat naar de eindtoestand.
Formeel definiëren we deze taal als volgt:
L={x ∈ {a,b}* : x bevat de substring bab}
Het sterretje betekent: alle mogelijke strings die met a,b gemaakt kunnen worden.
We passen nu de volgende strategie toe. Zodra een string een b bevat springt de automaat in toestand b... . Vanaf hier wordt vanaf elke b nu gechecked of er een a met daarna een b volgt. Als dat zo is springt de automaat in de eindtoestand (invoer van a of b daarna maakt niet meer uit). Als dat niet zo is wordt opnieuw verwezen naar de begintoestand.
Het complement van een automaat
In de laatste opgave hebben we een dfa gemaakt die de automaat precies omdraait. Deze accepteert alleen strings zonder sos. We noemen dit het complement van de taal L.
We konden dit bereiken door de eindtoestanden om te draaien. Dus de bestaande eindtoestand werd een gewone toestand en alle overige toestanden werden eindtoestanden. Er is een manier om dit op te schrijven.
De definitie van een automaat is:
M = {Q, ∑, δ, q0, F }
Alle toestanden waren: Q
De verzameling eindtoestanden zijn: F
Alle eindtoestanden omkeren schrijf je op met Q-F.
De defintitie wordt dus M' = {Q, ∑, δ, q0, Q-F }
Het complement geef je aan met een '.
Reguliere talen
Iedere eindige automaat accepteert een of andere vorm van een taal. Als je alle eindige automaten bij elkaar neemt kun je spreken van de familie van reguliere talen. Wanneer is een taal regulier? Antwoord: een taal is regulier als er een eindige automaat voor gevonden kan worden. We zullen dit aantonen met een voorbeeld.
Stel dat we de volgende taal hebben gedefiniëerd:
L = {awa : w ∈ {a,b}*}
Deze definitie geeft aan dat iedere string moet beginnen en eindigen met een a. Hoe gaan we daar een dfa voor maken in JFlap? We zullen dat stap voor stap uitleggen.
Begin met het maken van een splitsing. Als de string met een b begint kan de string niet worden geaccepteerd en kun je hier een trapstate voor maken.
Nu je het beginkarakter hebt maakt het niet uit welke string er vervolgens wordt geconstrueerd.
Als laatste moet er nog een constructie worden gemaakt om de automaat eindig te maken zodat alleen een string die eindigt op een a wordt geaccepteerd.
Automaten 2
Niet-deterministische eindige automaten
In dit deel zullen we de niet-deterministische automaten gaan bestuderen. We zullen daar vanaf nu de afkorting nfa (nondeterministic finite automaton) voor gebruiken zoals ook al in deel 2 is genoemd. Nfa's zijn complexere automaten. Bovendien lijken ze onzinnig. Toch zullen we zien dat ze erg nuttig kunnen zijn.
Normaal gesproken denk je aan een computer als een deterministische automaat, dus een apparaat wat maar op één manier een invoerstring kan behandelen. Bij een dfa heet dat een wandeling door de graaf. Deze wandeling kan maar op één manier gemaakt worden. Bij een nfa is dat niet zo. Het verschil met een dfa is dat de wandeling op meerdere manieren gemaakt kan worden. Zodra één wandeling leidt tot een eindtoestand, wordt de taal geaccepteerd.
Hieronder een voorbeeld van een nfa . Deze automaat leidt bij invoer van de string aaaa tot meerdere toestanden. Als één van deze toestanden leidt tot een eindtoestand, wordt de taal geaccepteerd.
De string aaaa leidt tot meerdere eindtoestanden en wordt dus geaccepteerd.
De lambda overgang
De lambda is de 11e letter van het Griekse alfabet en schrijf je als λ. De λ staat voor lege string. Beschouw het volgende voorbeeld:
Bij invoer van de string abab springt de automaat meteen in twee toestanden. Je zou de string ook zo kunnen lezen λabab.
De eeste 2 toestanden zijn nu als volgt:
Dit is de situatie voordat de string is gelezen. De automaat maakt dus een keuze tussen q0 of q2.
Bij het lezen van de a loopt de automaat vast bij de overgang δ(q2, a). Dit is overigens de manier waarop je dit opschrijft. De overgang δ(q0, a) leidt tot q1. Kijk maar in onderstaand voorbeeld.
Bij het lezen van b zie je weer dezelfde beginsituatie ontstaan maar dit komt ook door de overgang δ(q1, b) = {q0, q2}
Uiteindelijk wordt de taal geaccepteerd omdat δ(q0, abab) leidt tot q0.
Met andere woorden:
De lambda-overgang wordt altijd gelezen en maakt dat een automaat in twee toestanden tegelijk komt. Uit de opdrachten zal het je waarschijnlijk nog duidelijker worden.
Van een nfa een dfa maken
Stel dat we de volgende nfa hebben gemaakt.
Hoe kun je zien dat het een nfa is? We zien dat als we de string a invoeren dat de automaat komt in twee toestanden: δ(q0, a) = {q1,q2}. Hieronder zullen we dit uitleggen o.a. aan de hand van een tabel:
Bij het lezen van de eerste a komt de nfa vanuit q0 in twee toestanden, namelijk q1 en q2. Dit schrijven we op in onderstaande tabel:
lezen | toestanden
q0
q1
q2
a
q1, q2
b
We kunnen dit als een dfa construeren door gewoon een nieuwe toestand te maken die we {q1,q2} noemen:
We maken dus van de verzameling {q1,q2} een nieuwe toestand en schrijven dit ook in de tabel. Merk op dat de nieuwe toestand {q1,q2} een eindtoestand is. Als in de originele nfa één van de twee toestanden een eindtoestand is dan is dat ook in de geconverteerde dfa.
We kunnen in JFlap de situatie {q1, q2} ook illustreren in de originele nfa:
Nu gaan we verder. We kunnen ook een b invoeren. De automaat komt dan ook in de eindtoestand.
Dit schrijven we ook weer in de tabel.
inlezen
q0
q1
q2
a
{q1, q2}
b
{q1}
We moeten nu gaan kijken wat de automaat verder doet. Wat gebeurt er met een a vanuit zowel q1 als q2? Je moet dus in twee situaties tegelijk kijken. We zullen eerst in de tabel invullen wat er met een a gebeurt.
inlezen
q0
q1
q2
{q1, q2}
a
{q1, q2}
∅
{q1}
{q1}
b
(q1}
Je neemt dus de verzameling van q1 en q2 en schrijft dat in een nieuwe kolom.
Met de b gebeurt het volgende:
inlezen
q0
q1
q2
{q1,q2}
a
{q1, q2}
∅
{q1}
{q1}
b
(q1}
∅
∅
∅
Dit levert uiteindelijk bedoelde dfa op waarbij er dus geen pijl loopt voor bij vanuit {q1,q2} naar {q1}.
Merk ook op dat er in de tabel 3 overgangen staan. Dit is precies gelijk aan het aantal overgangen in de geconstrueerde dfa.
Dit lesmateriaal is gepubliceerd onder de Creative Commons Naamsvermelding 4.0 Internationale licentie. Dit houdt in dat je onder de voorwaarde van naamsvermelding vrij bent om:
het werk te delen - te kopiëren, te verspreiden en door te geven via elk medium of bestandsformaat
het werk te bewerken - te remixen, te veranderen en afgeleide werken te maken
voor alle doeleinden, inclusief commerciële doeleinden.
