3. Automatentheorie -> Epsilon-NEA in NEA wandeln

Automatentheorie -> Epsilon-NEA in NEA wandeln

  • V

    Ist das Bild jetzt besser sichtbar?
    http://www.bilder-space.de/show_img.php?img=dd6460-1306605569.jpg&size=original

    Hier die Definition der beiden genannten Mengen:

    predϵ(q)={p∈Q∣q∈ϵc(p)}pred_{\epsilon}(q) = \{ p \in Q | q \in \epsilon_c (p) \}

    succϵ(q′)={p∈Q∣p∈ϵc(q′)}succ_{\epsilon}(q') = \{ p \in Q | p \in \epsilon_c (q') \}

    Wenn nun meine oben genannten Übergänge stimmen sollten, dann muss ich für diese 3 Übergänge jeweils die zwei verschiedenen Mengen aufstellen. In der Art:

    B \stackrel{0}{\to} C:$$ $$ pred_{\epsilon}(B) = \{...\} $;$ $$ succ_{\epsilon}(C) = \{...\} D \stackrel{1}{\to} C:$$ $$ pred_{\epsilon}(D) = \{...\} $;$ $$ succ_{\epsilon}(C) = \{...\} D \stackrel{1}{\to} B:$$ $$ pred_{\epsilon}(D) = \{...\} $;$ $$ succ_{\epsilon}(B) = \{...\}

    q ist (irgend-)ein Zustand und q' ist der entsprechende Folgezustand. Q ist die Menge aller Zustände des Automaten. Was allerdings p beschreiben soll verstehe ich nicht so ganz...

    Ich hoff ihr helft mir noch weiter!

    0
  • C

    Wenn ich das richtig verstehe, stellt $$ \epsilon_c (p) $$ die Menge aller Zustände dar, die nur über ε-Übergänge von p aus erreichbar sind - der Rest ist eine typische Schreibung für Mengen {x|e} bezeichnet die Menge aller x, die Eigenschaft e erfüllen.

    Das heißt für dich, pred(q) ist die Menge aller Zustände, von denen du ohne Eingabe nach q kommst, und succ(q') die Menge aller Zustände, die du von q' erreichst. Um mal dein Beispiel zu bemühen: Für die Kante B->C hast du die pred(B)={A, B} und succ(C)={C, D}.

    PS: Bei deiner Liste dort oben hast du die Schleife A->A vergessen 😉

    0
  • V

    Wäre nett wenn ihr das kurz überprüfen könntet:

    B \stackrel{0}{\to} C:$$ $$pred_{\epsilon}(B) = \{A,B\};$$ $$succ_{\epsilon}(C) = \{C,D\} D \stackrel{1}{\to} C:$$ $$pred_{\epsilon}(D) = \{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\}

    Stimmt das so?

    0
  • C

    vip@r schrieb:

    D \stackrel{1}{\to} C:$$ $$pred_{\epsilon}(D) = \{C,D\};$$ $$succ_{\epsilon}(C) = \{C,D\} D \stackrel{1}{\to} B:$$ $$pred_{\epsilon}(D) = \{A,C,D\};$$ $$succ_{\epsilon}(B) = \{B\}

    Fällt dir hier etwas an den Vorgängern auf?

    0
  • V

    Naja, bei der ersten Zeile, ist die Vorgängermenge die gleich wie die Nachfolgermenge... Und bei beiden Mengen ist jeweils der Vorgänger gleich.Aber ansonsten wüsste ich nicht was da jetzt sein soll.

    0
  • C

    Worauf ich hinaus wollte: Du hast für pred(D) zwei verschiedene Ergebnisse erhalten, davon kann nur eins korrekt sein.

    0
  • V

    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?

    0
  • C

    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)

    0
  • V

    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.

    0
  • V

    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?

    0
  • C

    Ja, für Eigenschleifen gelten die selben Regeln wie für "normale" Kanten, also können sie auch kritisch sein.

    0
  • V

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

    0
  • C

    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 😃

    0
  • V

    Nein wie speziell muss ich denn mit den akzeptierende Zuständen umgehen?

    0
  • 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
Anmelden zum Antworten