3. Automatentheorie -> Epsilon-NEA in NEA wandeln

Automatentheorie -> Epsilon-NEA in NEA wandeln

  • 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