Automatentheorie -> Epsilon-NEA in NEA wandeln
-
Aber das sind doch Epsilon-Transitionen, die sollen ja wegfallen... Das würde jetzt mein gesamtes "Weltbild" zerstören!
Hier das Bild: http://imageshack.us/photo/my-images/146/21606097.jpg/
Falls dieser NEA nun richtig sein sollte, dann will ich den jetzt noch in einen DEA umwandeln. Ich hab das mal über die Potenzmengenkonstruktion gemacht; ist aber schon länger her; soll ich den DEA wieder zeichnen und ich lad dann wieder ein Bild hoch. Wärst du dann so nett und würdest das auf Richtigkeit überprüfen?
-
So sieht der DEA jetzt mal aus: http://imageshack.us/photo/my-images/705/91771031.jpg/
Der ist zwar jetzt eigentlich noch gar nicht ganz fertig; der Zustand F fehlt noch. Ich weiß aber nicht wie ich den jetzt in die Potenzmengenkonstruktion da mit aufnehmen soll!
Kannst du mir helfen?
Edit:
Mir ist leider gerade erst aufgefallen, dass beim NEA der akzeptierende Zustand nicht markiert ist, bleibt ja E. Beim DEA leider das gleiche. Hier ist es natürlich die Potenzmenge {E}. Ich werd die Bilder aber jetzt nicht mehr neu uppen!
-
CStoll schrieb:
(btw, ich bin gerade am Überlegen, ob die Kanten von und nach F auch kritisch sein könnten)
Hm, kannst du darauf vielleicht nocheinmal Bezug nehmen? mich würde sehr interessieren wieso du meinst, dass diese epsilon-Kanten noch zu den kritischen Kanten gehören, insbesondere deswegen weil das ja epsilon-Transitionen sind!
Danke!
-
In deiner Beschreibung des Algorithmus hattest du damit angefangen:
vip@r schrieb:
- Suche alle Kanten, bei denen entweder eine Epsilon-Transition in in einem Zustand q endet, oder aber eine in einem Folgezustand q' beginnt. Diese Kanten nennt man kritische Kanten.
dort steht nirgends, daß ε-Kanten nicht berücksichtigt werden sollen. Und meine eigenen Berechenbarkeits-Vorlesungen liegen leider zu lange zurück, um mich daran zurückzuerinnern.
-
Ich hätte hier nochmal einen epsilon-NEA:
http://imageshack.us/photo/my-images/232/10425562.jpg/
Ich hab hier wieder versucht alle kritischen Kanten inkl. den Mengen rauszufinden. Gefunden hab ich bis jetzt diese 3 bei denen ich mir auch sehr sicher sind, dass das welche sind:
q3 -> q2 mit 0: pred(q3)={q0, q3}; succ(q3)={q3}
q1 -> q2 mit 0: pred(q1)={q1, q2}; succ(q2)={q2, q1}
q1 -> q1 mit 1: pred(q1)={q1, q2}; succ(1)={q1}Wo ich mir allerdings grad nicht sicher bin ist, ob die Kante q2 -> q1 mit 1 auch eine ist...
Könnt ihr mir helfen?
-
vip@r schrieb:
Wo ich mir allerdings grad nicht sicher bin ist, ob die Kante q2 -> q1 mit 1 auch eine ist...
q2->q1 ist keine kritische Kante, aber die Kante q1->q0 hast du übersehen
-
Shit. Das mir jetzt dieses Zeug nie richtig und komplett gelingen mag!
Ich hab hier nochmal alle zusammengetragen:
q3 -> q2 mit 0: pred(q3)={q0, q3}; succ(q3)={q3}
q1 -> q2 mit 0: pred(q1)={q1, q2}; succ(q2)={q2, q1}
q1 -> q1 mit 1: pred(q1)={q1, q2}; succ(1)={q1}
q1 -> q1 mit 0: pred(q1)={q1, q2}; succ(q0)={q0}Stimmt das jetzt so?
In meinen Vorlesungsfolien steht zu den kritischen Kanten das hier: Suche alle Kanten q -> q' mit a, bei denen entweder eine epsilon-Transition in q endet oder aber eine in q' beginnt (diese Kanten nennt man kritischen Kanten). Wenn ich mir nun so die ganzen letzten Beispiel so durchschaue, dann tritt eigentlich nie der Fall "oder aber eine in q' beginnt" ein. Warum ist das so? Was sagst du dazu?
-
Jetzt mußt du nur noch (a) die richtigen Nachfolger-Mengen berechnen (bei der ersten Kante benötigst du succ(q2) und (b) die Nachfolger richtig ermitteln (schau dir nochmal succ(q0) genau an).
vip@r schrieb:
Warum ist das so? Was sagst du dazu?
Schlecht gewählte Beispiele
-
q3 -> q2 mit 0: pred(q3)={q0, q3}; succ(q2)={q2, q1}
q1 -> q2 mit 0: pred(q1)={q1, q2}; succ(q2)={q2, q1}
q1 -> q1 mit 1: pred(q1)={q1, q2}; succ(1)={q1}
q1 -> q1 mit 0: pred(q1)={q1, q2}; succ(q0)={q0, q3}Jetzt stimmt's aber...
-
Ich hätte hier nochmal einen neuen Automaten: http://imageshack.us/photo/my-images/4/64354067.jpg/
Die kritischen Kanten bei denen ich mir richtig sicher bin wären diese hier:
D -> 1 -> A:
B -> 0 ->
C -> 1 -> B:Wo ich grad schon länger dran rumrätsle ist, ob diese Kanten nicht auch welche wären:
A -> 1 -> B: (weil man hier ja die epsilon-Transition von A nach B und die weitere epsilon-Transition B nach C hat...)
C -> 1 -> A: (weil man hier ja die epsilon-Transition von C nach D und die weitere epsilon-Transition D nach D hat...)
A -> 1 -> A: (weil mit epsilon-Transitionen von A über B über C über D mit einer 1 wieder nach A kommen würde)
B- > 1 -> A: (mit epsilon-Transition von B über C über D mit 1 nach A)
D -> 1 -> A: (mit epsilon-Transition von D mit 1 nach A)
B -> 1 -> B: (mit epsilon-Transition B über C mit 1 nach
Das sollten jetzt alle gewesen sein!
Könnt ihr mir helfen?
-
nein, eben für diese Kanten baust du ja prec und succ...
-
Ah, ok. Jetzt glaub ich steig ich langsam wirklich richtig dahinter
Also stimmen die 3 kritischen Kanten von weiter ob?
So sieht's dann aus:
D -> 1 -> A: pred(D)={A,B,C,D}; succ(A)={A,B,C,D}
B -> 0 -> pred(B)={A,B}; succ(D)={D}
C -> 1 -> B: pred(C)={A,B,C}; succ(B)={B,C,D}Könnte das jemand überprüfen?
-
Hey Leute!
Ich hab hier wieder einen epsilon-NEA. Ich versuch grad wieder die kritischen Kanten zu suchen. Ich bin auf diese hier gestoßen (incl. der pre.- und succ.-Mengen):
B -> 0 -> C: pred(B)={A,B}; succ(C)={C,D}
D -> 1 -> C: pred(D)={A,C,D}; succ(C)={C,D}
D -> 1 -> B: pred(D)={A,C,D}; succ(B)={B}
A -> 0,1 -> A: pred(A)={A}; succ(A)={A,B,D}
B -> 0 -> C: pred(B)={A,B}; succ(C)={C,D}Hier noch der Automat: http://imageshack.us/photo/my-images/842/33018413.jpg
Stimmt das soweit?
