3. Automatentheorie -> Epsilon-NEA in NEA wandeln

Automatentheorie -> Epsilon-NEA in NEA wandeln

  • V

    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?

    0
  • C

    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.

    0
  • V

    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?

    0
  • C

    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)

    0
  • V

    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?

    0
  • V

    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!

    0
  • V

    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!

    0
  • C

    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.

    0
  • V

    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?

    0
  • C

    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

    0
  • V

    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?

    0
  • C

    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 🕶

    0
  • V

    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...

    0
  • V

    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?

    0
  • O

    nein, eben für diese Kanten baust du ja prec und succ...

    0
  • V

    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?

    0
  • V

    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?

    0
Anmelden zum Antworten