Automaten aus gegebener Sprache konstruieren
-
Es fehlt nichts an dem Automaten - da sind im Gegenteil Kanten zu viel (eine der beiden 0-Kanten vom Startzustand). Aber wie man aus einem NEA einen DEA bildet, hast du afair auch schon behandelt.
-
da sind im Gegenteil Kanten zu viel (eine der beiden 0-Kanten vom Startzustand)
Dann gehe ich mal davon aus, dass die 0 der Schleife zu viel ist. Ich denke aber nicht, dass du nun DEA zu einen NEA von Hand gewandelt hast. Bist du vielleicht deswegen so schnell drauf gekommen weil eine 0,1-Schleife am Startzustand eines NEA immer steht und beim DEA nicht? Oder ist das Schwachsinn?
-
Nein, ich bin darauf gekommen, weil von deinem Startzustand zwei 0-Kanten vorkommen - sowas ist bei einem NEA erlaubt, aber nicht bei einem DEA. Aber nachdem du schon einen NEA hast, kannst du den auch weiterverarbeiten (Stichwort: Potenzmengen-Konstruktion).
-
Ich hab's dann mal so versucht: http://imageshack.us/photo/my-images/714/47478780.jpg/
Richtig?
-
Erstens sind die Bezeichnungen davor genau verkehrt herum und zweitens scheint der DEA auch nicht ganz richtig zu sein - dort fehlen imho eine ganze Menge an Kanten.
-
sorry, aber ich wüsste nicht wo ich da noch mehr kanten haben soll...
-
Hast du denn noch deine Unterlagen zur Umwandlung von NEA nach DEA greifbar? Ich skizziere mal den Anfang:
Startzustand: q0 -> {q0}
Zustand {q0}: 0: {q0, q1}, 1: {q0}
Zustand {q0, q1}: 0: {q0, q1}, 1: {q0, q2} //Nachfolger sind alle, die von einem der genannten Zustände erreichbar sind
...
-
So, noch ein Versuch. Jetzt sollte es aber stimmen...
-
Fehlt noch eine Eigenschleife - und einige Kantenbezeichnungen
-
genau deswegen hab ich den link auch wieder raus
-
Hier nochmal. Ich hoff dass das jetzt endlich stimmt:
http://imageshack.us/photo/my-images/87/45896514.jpg/
Wie ist das jetzt eigentlich wenn ich vomm letzten Zustand mit 1 alle Möglichkeiten durchprobiere? Teilzustand q0 im letzten Zustand des DEAs komm ich ja mit ner 1 auf q0 nach vorne. Was ist dann aber mit q2? Da komm ich ja laut NEA mit ner 1 nicht weiter... Wird dann einfach nix rangeschrieben? Stimmt das so?
-
vip@r schrieb:
Ich komm jetzt auf:
n%5 | n0%5 | n1%5 ------------------ 0 | 0 | 1 1 | 2 | 3 2 | 4 | 0 3 | 1 | 2 4 | 3 | 4Stimmt's jetzt? Wenn ja, wie kann man nun daraus den DEA ablesen?
Ich hab die Tabelle mal automatenähnlich gemalt: http://tinypic.com/view.php?pic=30wmlpx&s=7
Hübsch, gell?
-
Is aber schon falscher Thread, oder? Und warum kommst du von q3 auf q1 mit einer 0? Bei mir steht in der Tabelle in der 4. Zeile und in der 2. Spalte eine 1...
-
vip@r schrieb:
Is aber schon falscher Thread, oder?
Kann wohl sein, daß ich was verpeilt habe. Nichts für Ungut.
vip@r schrieb:
Und warum kommst du von q3 auf q1 mit einer 0? Bei mir steht in der Tabelle in der 4. Zeile und in der 2. Spalte eine 1...
Von q3 kommst Du durch eine 0 doch auch zu q1.
