3. Automatentheorie -> Epsilon-NEA in NEA wandeln

Automatentheorie -> Epsilon-NEA in NEA wandeln

  • V

    Hi Leute!

    Ich soll einen Epsilon-NEA in einen NEA wandeln. Hier der Link zum Epsilon-NEA: http://imageshack.us/photo/my-images/827/74436500.jpg/

    Wie finde ich hier nun die kritischen Kanten raus? Welches Schema benutzt ihr da? Ich hab natürlich mal angefangen und diese Kanten gefunden:

    A \stackrel{1}{\to} C D \stackrel{1}{\to} B B \stackrel{0}{\to} C

    Sind die soweit richtig? Könnt ihr mir helfen?

    PS: Warum funktioniert mein Latex-Code hier nicht?

    0
  • C

    Was meinst du mit "kritische Kanten"? Die Epsilon-ÜBergänge kann man doch eigentlich nicht übersehen (bei deinem Beispiel A->B, A->D und C->D) - um die loszuwerden, mußt du alle vom Ziel ausgehenden Kanten kopieren auf den Ursprung (sind ja nicht so viele).

    0
  • V

    Dass bei meinem Beispiel A->B, A->D und C->D die Epsilon-Übergänge sind, ist klar.

    Was meinst du nun mit, "... mußt du alle vom Ziel ausgehenden Kanten kopieren auf den Ursprung"? Kannst du darauf genauer eingehen?

    Wir haben in der Vorlesung folgendes Schema bekommen:

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

    - Bestimme für jede kritische Kante die predecessor- sowie successor-Menge.

    - Bilde aus predecessor sowie successor Menge das kartesische Produkt.

    - Zeichne die Menge des entstandenen kartesischen Produkts pro kritische Kante ein

    - Lösche Epsilon-Transitionen -> NEA

    Die Definition der predecessor sowie successor Mengen kann ich hier leider nicht posten, da anscheinend Latex hier nicht funktioniert...

    0
  • C

    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.

    Da steht doch genau, was eine kritische Kante ist: X->Y ist kritisch, wenn es eine Epsilon-Kante von irgendwo nach X oder von Y nach irgendwo gibt (das sind in deinem Beispiel alle "normalen" Kanten)

    PS: Was mit dem Latex-Code los ist, kann ich dir leider nicht beantworten, aber vermutlich hast du einen Fehler drin

    0
  • V

    Das heißt, die kritischen Kanten sehen so aus:

    B->C mit 0, weil in B eine Epsilon-Transition endet?

    D->C mit 1, weil in D eine Epsilon-Transition endet?

    D->B mit 1, weil in D eine Epsilon-Transition endet?

    Stimmt das soweit?

    0
  • ?

    Das Bild von dem Automaten wird bei mir in keinem Browser korrekt angezeigt. Es fehlen die meisten Kanten. Bitte prüfe das mal dann kann ich evtl. was dazu sagen.

    EDIT: Oder schreibe die Übergangsrelation als Tabelle. Geht auch.

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