Automatentheorie -> Epsilon-NEA in NEA wandeln
-
Worauf ich hinaus wollte: Du hast für pred(D) zwei verschiedene Ergebnisse erhalten, davon kann nur eins korrekt sein.
-
Mal ganz dumm gefragt: Auch wenn ich zwei verschiedene Ergebniss erhalten habe, ist das aber jetzt nicht falsch, oder? Muss man jetzt noch unterscheiden welches das Richtige ist? Wenn ja wie geht das?
ODER:
Stimmen meine "kritischen Kanten" nicht? Eine zuviel?
-
Bei der Bestimmung der Vorgängermenge ist es egal, für welche kritische Kante du das gerade berechnest, also können da, wenn du alles korrekt gemacht hast, keine unterschiedlichen Werte herauskommen.
(Tip: beim ersten fehlt ein Wert)
-
B \stackrel{0}{\to} C:$$ $$pred_{\epsilon}(B) = \{A,B\};$$ $$succ_{\epsilon}(C) = \{C,D\} D \stackrel{1}{\to} C:$$ $$pred_{\epsilon}(D) = \{A,C,D\};$$ $$succ_{\epsilon}(C) = \{C,D\} D \stackrel{1}{\to} B:$$ $$pred_{\epsilon}(D) = \{A,C,D\};$$ $$succ_{\epsilon}(B) = \{B\} A \stackrel{0,1}{\to} A:$$ $$pred_{\epsilon}(A) = \{A\};$$ $$succ_{\epsilon}(A) = \{A,B,D\}So sollte es jetzt stimmen. Jetzt hab ich beim zweiten wie beim dritten die gleiche Vorgänger-Menge.
-
Was ich hier immer noch nicht ganz verstanden habe, ist, warum $$A \stackrel{0,1}{\to} A:$$ auch eine "kritische Kante" ist. Liegt das daran weil quasi die Epsilon-Transition in diesem Zustand startet und wegen der Eigeschleife somit der Zustand A zugleich der nachfolgende Zustand q' ist?
Stimmt das so?
-
Ja, für Eigenschleifen gelten die selben Regeln wie für "normale" Kanten, also können sie auch kritisch sein.
-
Ich hätte hier nochmal einen neuen Automaten. Vielleicht magst du mit mir hier nochmal die kritischen Kanten durchgehen; ich finde hier nämlich nur eine einzige... Und irgendwie kommt mir das zu wenig vor.
Link zum Bild: http://imageshack.us/photo/my-images/37/29617714.jpg/
meine Kante:
D \stackrel{0}{\to} E:$$ $$pred_{\epsilon}(D) = \{A,D\};$$ $$succ_{\epsilon}(E) = \{E\}Ich denke dass die stimmen dürfte, nur fehlen da wahrscheinlich noch ein paar. Ich weiß aber nicht recht welche das sein sollen...
Edit: Latex geht anscheinend immer nocht nicht; hab da letztens an das Forum schon mal eine Nachricht geschrieben...
-
Ja, D->E ist auch die einzige kritische Kante, die mir auffällt (liegt wohl auch daran, daß F->D die einzige ε-Kante ist, die einen Vorgänger oder Nachfolger hat).
PS: Hast du auch daran gedacht, wie du mit den akzeptierenden Zuständen umgehen mußt?
Edit: Wenn Latex nicht geht, dann verwende doch normalen Fließtext
-
Nein wie speziell muss ich denn mit den akzeptierende Zuständen umgehen?
-
Wenn ich jetzt die Kante
D -> E mit 0: pred(D) = {A,D}; succ(E) = {E}
in den Graphen einzeichne und die Epsilon-Transitionen lösche, dann fällt ja F komplett weg... Stimmt das wirklich so?
-
In deinem ursprünglichen ε-NFA kannst du ohne Eingabe von A in den Endzustand E gelangen, also muß A auch ein Endzustand im (ε-freien) neuen NFA werden.
PS: Was mir noch aufgefallen ist (unverarbeiteten Latex-Code zu lesen ist gar nicht so einfach :D): In der Vorgänger-Menge pred[e]epsilon[/e](D) sollte F auch noch enthalten sein.
-
Du meinst also so:
D -> E mit 0: pred(D) = {A,D,F}; succ(E) = {E}
Warum muss F mit rein? Das hab ich doch beim ersten Automaten in diesem Thread auch nicht gemacht, oder?
Edit:
Ist jetzt klar; ich gehe ja von A über F nach D bei der pred.-Menge...Edit:
Ich schieb mal schnell ein Bild vom neue entstandenen NEA hoch, ok?
-
vip@r schrieb:
Du meinst also so:
D -> E mit 0: pred(D) = {A,D,F}; succ(E) = {E}
Warum muss F mit rein? Das hab ich doch beim ersten Automaten in diesem Thread auch nicht gemacht, oder?
Ja - bei dem anderen Automaten hattest du ja auch keine Konstellation wie hier, wo zwei ε-Kanten hintereinander kommen.
(btw, ich bin gerade am Überlegen, ob die Kanten von und nach F auch kritisch sein könnten)
-
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?
