| Die letzten 10 Beiträge |
| 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
Karlito hat dieses Bild (verkleinerte Version) angehängt:
|
| 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 |
| 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 |
| Haniball |
Danke. Ich habe jedoch mal das Wort "aabb" getestet. Im NFA wird es nicht akzeptiert. Im neuen DFA jedoch schon. |
| 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
![[latex]<br />
\begin{tabular}[t]{r|cc}<br />
& a & b \\<br />
\hline \\<br />
\{S0\} & \{S1\} & \{S2\} \\<br />
\{S1\} & \{S1\} & \{S1,S2\} \\<br />
\{S2\} & \{S3\} & \{S3\} \\<br />
\{S1,S2\} & \{S1,S3\} & \{S1,S2,S3\} \\<br />
\{S1,S3\} & \{S1\} & \{S1,S2,S3\} \\<br />
\{S1,S2,S3\} & \{S1,S3\} & \{S1,S2,S3\} \\<br />
\{S3\} & / & \{S2\} \\<br />
/ & / & / \\<br />
\end{tabular}<br />
[/latex]](http://www.matheboard.de/latex2png/latex2png.php?<br />
\begin{tabular}[t]{r|cc}<br />
& a & b \\<br />
\hline \\<br />
\{S0\} & \{S1\} & \{S2\} \\<br />
\{S1\} & \{S1\} & \{S1,S2\} \\<br />
\{S2\} & \{S3\} & \{S3\} \\<br />
\{S1,S2\} & \{S1,S3\} & \{S1,S2,S3\} \\<br />
\{S1,S3\} & \{S1\} & \{S1,S2,S3\} \\<br />
\{S1,S2,S3\} & \{S1,S3\} & \{S1,S2,S3\} \\<br />
\{S3\} & / & \{S2\} \\<br />
/ & / & / \\<br />
\end{tabular}<br />
)
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
Karlito hat dieses Bild (verkleinerte Version) angehängt:
|
| 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
Haniball hat dieses Bild (verkleinerte Version) angehängt:
|
| 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 |
| 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 |
| 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 |
| 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 |
| Es sind weitere Beiträge zu diesem Thema vorhanden. Klicken Sie hier, um sich alle Beiträge anzusehen. |
|
|
