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.