Informatiker Board | Druckvorschau: Aufgabe zu NFA nach DFA konvertieren

Geschrieben von Haniball am 06.06.2011 um 23:03:

Aufgabe zu NFA nach DFA konvertieren

Hi,

ich habe auf einem Übungsblatt folgende Aufgabenstellung:

Gegeben sei de folgende nichtdeterministische endliche Automat A:

Eingabealphabet S = {a, b}
Zustandsmenge S = {s0, s1, s2, s3}
Anfangszustand s0
Endzustände F = {s2}

Zustandsübergangstabelle:

. s0 s1 s2 s3
---------------------------------------
a {s1} {s1} {s3} /
b {s2} {s1,s2} {s3} {s2}

a) Konstruieren Sie einen zu diesen Automaten äquivalenten deterministischen Automaten.

Kann mir jemand ein Verfahren zeigen, wie man den DFA konstruieren kann. Ist {s1,s2} ein Zustand?

Geschrieben von Haniball am 06.06.2011 um 23:36:

RE: Aufgabe zu NFA nach DFA konvertieren

Hi nochmal,

ich habe mir folgenden Automaten daraus mit Dot gezeichnet. Ist das richtig so?

Grüße,
Haniball

Geschrieben von Karlito am 07.06.2011 um 20:57:

Hallöle,

danke für DOT, das kannte ich noch nicht Augenzwinkern

Wenn ich deine Tabelle richtig interpretiere, ist dein Zustandsautomat falsch, da man mit "b" von S1 nach S1 und S2 gelangt und nicht, wie du es gezeichnet hast, von S1 mit "a oder b" nach s2.

Den DFA konstruiert man, indem man für jeden Zustand die Menge der erreichbaren Zustände angibt und diese Menge dann wieder als neuen Zustand auffasst. Dabei sind alle neuen Zustände, welche einen Finalzustand enthalten, wieder Finalzustände.
Weiterhin wird für fehlende Übergänge (wie hier z.B. von S3 mit "a") ein neuer Zustand eingeführt, welcher ein "Papierkorbzustand" ist. Von diesem aus gehen alle Transitionen wieder in den Papierkorbzustand.

Man kann dies leicht mit einer Tabelle konstruieren:
$[latex] \begin{tabular}[t]{r|cc} $\circ $ & a & b \\ \hline \\ \{S0\} & \{S1\} & \{S2\} \\ \{S1\} & \{S1\} & \{S1,S2\} \\ \{S2\} & \{S3\} & \{S3\} \\ \{S1,S1\} & \{S1\} & \{S1,S2\} \\ \{S3\} & \{S4\} & \{S2\} \\ \{S4\} & \{S4\} & \{S4\} \\ \end{tabular} [/latex]$

Daraus lässt sich dann der DFA herleiten aufzeichnen. Siehe Anhang.

Hoffe ich habe keine Fehler gemacht und meine Erklärung ist verständlich.

VG,

Karlito

Geschrieben von Karlito am 07.06.2011 um 21:50:

Achso eins noch: bitte nicht den Anfangszustand vergessen! Ich glaube das wollen alle Profs sehen..

(Kann sein, dass du nur nicht wusstest wie die in DOT notiert werden...)

VG,

Karlito

Geschrieben von Haniball am 07.06.2011 um 22:24:

Hi,

danke für die Umfassende Tabelle und Antwort. Wie kommst du in der 4. Zeile auf {s1,s1}? Du meintest sicherlich {s1,s2}? Dann wäre das verständlich. Ansonsten, wie kommst du bei {s1,s2} zu a = {s1} und b = {s1,s2} (sorry für die grauenhafte schreibweise)?
(wie hast du die Tabelle gemacht?)

Danke und Grüße

Geschrieben von Karlito am 08.06.2011 um 08:59:

Hallöchen,

ich sehe gerade, da hat sich der Fehlerteufel eingeschlichen. natürlich hast du recht, es sollte {s1,s2} heißen. Weiterhin ist natürlich unklar, wie man von {s1,s2} nach nur nach s1 kommt. Hier ergibt sich natürlich ein neuer Zustand {s1,s3}, da man von s2 zusätzlich noch mit a nach s3 kommt. Weiterhin ergibt sich so für b von {s1,s2} die Menge {s1,s2,s3} .Leider habe ich gerade keine Zeit das noch mal sauber aufzuschreiben. Hoffe die erklärung reicht aus.

Vlt noch mal kurz zur Konstruktion der Tabelle: links stehen alle zustände deines NFA und rechts daneben alle zustände, die du mit den entsprechenden Transitionen (wie im Tabellenkopf angegeben) erreichen kannst.
Ist hier eine Menge von Zuständen erreichbar, wird diese Menge als neuer Zustand aufgefasst und mit auf die linke Seite übernommen. Dann schaust du, welche Menge von Zuständen aus dieser Menge wieder mit den Transitionen erreichbar ist...

Sollte die Erklärung nicht ausreichen, mache ich es im laufe der Woche noch mal neu.

VG,

Karlito

Geschrieben von Karlito am 08.06.2011 um 09:13:

Eins noch: ergibt sich auf der rechten Seite die leere Menge, so wird die leere Menge zu einem neuen Zustand! (Ich hatte den einfach s4 genannt, so ist das vlt eingänglicher)

Hier noch ein Link: http://de.wikipedia.org/wiki/Potenzmengenkonstruktion

VG,

Karlito

Geschrieben von Haniball am 08.06.2011 um 23:13:

Hi,

ich bin zu folgendem DFA gekommen. Ist der so richtig. Wenn ja, wie erkenne ich hier, dass er nicht minimal ist, und wie minimiert man diesen?

s0 ist Startzustand.

Danke und Grüße

Geschrieben von Karlito am 09.06.2011 um 00:11:

Hallöle,

der Automat kann nicht richtig sein, da bei einem DFA immer Abgänge für jedes Alphabetzeichen exisitieren. Bei S3 fehlt dir der Übergang für "a" und bei S23 der übergang für a. Außerdem bekomme ich keinen Zustand S23

$[latex] \begin{tabular}[t]{r|cc} & a & b \\ \hline \\ \{S0\} & \{S1\} & \{S2\} \\ \{S1\} & \{S1\} & \{S1,S2\} \\ \{S2\} & \{S3\} & \{S3\} \\ \{S1,S2\} & \{S1,S3\} & \{S1,S2,S3\} \\ \{S1,S3\} & \{S1\} & \{S1,S2,S3\} \\ \{S1,S2,S3\} & \{S1,S3\} & \{S1,S2,S3\} \\ \{S3\} & / & \{S2\} \\ / & / & / \\ \end{tabular} [/latex]$

So, das dürfte es jetzt gewesen sein, wenn ich nicht wieder einen Fehler gemacht habe Augenzwinkern

Minimalisierung weis ich jetzt auch grad nicht. Da müsste ich mal im Skript nachschlagen. Da gab es eine bestimmte Reihenfolge der Schritte, die man einhalten muss...

VG,

Karlito

Geschrieben von Haniball am 09.06.2011 um 00:51:

Danke. Ich habe jedoch mal das Wort "aabb" getestet. Im NFA wird es nicht akzeptiert. Im neuen DFA jedoch schon.

Geschrieben von Karlito am 09.06.2011 um 09:05:

NFA:
a -> s1
a -> s1
b -> s1
b -> s2

Ich hatte dir geschrieben, dass ich deinen NFA unkorrekt finde und dir noch mal einen neuen erstellt. Bitte Kontrolliere das noch mal.

Du kannst doch auch noch für das erste b im Zustand S1 verbleiben. So wird das Wort akzeptiert.

DFA hast du ja selbst ermittelt...

VG,

Karlito