 Aufgabe zu NFA nach DFA konvertieren |
Haniball
Grünschnabel
Dabei seit: 06.06.2011
Beiträge: 7
 |
|
| 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?
|
|
06.06.2011 23:03 |
|
|
Haniball
Grünschnabel
Dabei seit: 06.06.2011
Beiträge: 7
|
|
|
|
06.06.2011 23:36 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallöle,
danke für DOT, das kannte ich noch nicht 
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]<br />
\begin{tabular}[t]{r|cc}<br />
$\circ $ & a & b \\<br />
\hline \\<br />
\{S0\} & \{S1\} & \{S2\} \\<br />
\{S1\} & \{S1\} & \{S1,S2\} \\<br />
\{S2\} & \{S3\} & \{S3\} \\<br />
\{S1,S1\} & \{S1\} & \{S1,S2\} \\<br />
\{S3\} & \{S4\} & \{S2\} \\<br />
\{S4\} & \{S4\} & \{S4\} \\<br />
\end{tabular}<br />
[/latex]](http://www.matheboard.de/latex2png/latex2png.php?<br />
\begin{tabular}[t]{r|cc}<br />
$\circ $ & a & b \\<br />
\hline \\<br />
\{S0\} & \{S1\} & \{S2\} \\<br />
\{S1\} & \{S1\} & \{S1,S2\} \\<br />
\{S2\} & \{S3\} & \{S3\} \\<br />
\{S1,S1\} & \{S1\} & \{S1,S2\} \\<br />
\{S3\} & \{S4\} & \{S2\} \\<br />
\{S4\} & \{S4\} & \{S4\} \\<br />
\end{tabular}<br />
)
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
Karlito hat diese Bilder (verkleinerte Versionen) angehängt:
 
|
|
|
07.06.2011 20:57 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
|
07.06.2011 21:50 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Karlito: 08.06.2011 09:20.
|
|
|
08.06.2011 08:59 |
|
|
Haniball
Grünschnabel
Dabei seit: 06.06.2011
Beiträge: 7
|
|
Danke. Ich habe jedoch mal das Wort "aabb" getestet. Im NFA wird es nicht akzeptiert. Im neuen DFA jedoch schon.
|
|
|
09.06.2011 00:51 |
|
|
Haniball
Grünschnabel
Dabei seit: 06.06.2011
Beiträge: 7
|
|
Ah. Jetzt sehe ich, dass es klappt. Ich bin mit den Buchstaben falsch durch den NFA gelaufen.
Ich werde mal heute Abend den Automaten versuchen zu minimieren und poste dann das Ergebnis.
Danke und Grüße
|
|
|
09.06.2011 16:44 |
|
|
|
