Aufgabe zu NFA nach DFA konvertieren |
| 06.06.2011, 23:03 | Auf diesen Beitrag antworten » |
| Haniball | 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:36 | Auf diesen Beitrag antworten » |
| Haniball | 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 |
| 07.06.2011, 20:57 | Auf diesen Beitrag antworten » |
| Karlito | 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: 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 |
| 07.06.2011, 21:50 | Auf diesen Beitrag antworten » |
| Karlito | 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 |
| Anzeige | |
|
|
|
| 07.06.2011, 22:24 | Auf diesen Beitrag antworten » |
| Haniball | 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 |
| 08.06.2011, 08:59 | Auf diesen Beitrag antworten » |
| Karlito | 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 |
| 08.06.2011, 09:13 | Auf diesen Beitrag antworten » |
| Karlito | 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 |
| 08.06.2011, 23:13 | Auf diesen Beitrag antworten » |
| Haniball | 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 |
| 09.06.2011, 00:11 | Auf diesen Beitrag antworten » |
| Karlito | 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 So, das dürfte es jetzt gewesen sein, wenn ich nicht wieder einen Fehler gemacht habe
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 |
| 09.06.2011, 00:51 | Auf diesen Beitrag antworten » |
| Haniball | Danke. Ich habe jedoch mal das Wort "aabb" getestet. Im NFA wird es nicht akzeptiert. Im neuen DFA jedoch schon. |
| 09.06.2011, 09:05 | Auf diesen Beitrag antworten » |
| Karlito | 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 |
| 09.06.2011, 16:44 | Auf diesen Beitrag antworten » |
| Haniball | 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 |
| 10.06.2011, 07:58 | Auf diesen Beitrag antworten » |
| Karlito | Ich komme auf die angehängte Lösung. Schritte: 1. Unerreichbare Zustände entfernen 2. Äquivalente Zustände zusammenfassen (War doch ni so kompliziert wie ich dachte) VG, Karlito |
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
