NEA zu DEA mit Epsilon

Bachelor Berechenbarkeit und Formale Sprachen
1

Goto Betreff

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

NEA zu DEA mit Epsilon
Hi,

Ich hab wieder mal eine Frage zu BFS: Im Skript auf Seite 51 wird ein NEA mit Epsilon Übergang zu einem DEA umgewandelt. Ich gehe dabei so vor, dass ich als erstes den NEA mit Epsilon Übergang zu einem NEA ohne Epsilon Übergang baue. Mein Automat ohne epsilon hat somit einen Übergang von q0 nach q0 mit Eingabe 0 und von q2 nach q1 mit Eingabe 0. Wenn ich daraus einen DEA bilde und diesen mit Abbildung 18 vergleiche fallen mir Unstimmigkeiten auf: Zustand q0 geht hier mit Eingabe 0 zur leeren Menge ( Bei mir geht q0 mit Eingabe 0 zu q0 ) und Zustand q0q1 geht mit Eingabe 0 zu q1q2 ( Bei mir geht q1q2 mit Eingabe 0 zu q1q2 ).
Stimmt hier etwas mit dem Skript nicht, oder ist meine Lösung falsch? Jedenfalls komme ich mit meiner Lösung auch wieder auf Abbildung 19 was mich ein wenig verwirrt.

Zur Umwandlung von NEA mit e zu NEA ohne e verwendet ich btw. folgende Vorgehensweise: http://www.info-wsf.de/index.php/Epsilon-NEA

3

Sie sollten keine Vorverarbeitung bei der Transformation durchführen. Insbesondere nicht, weil Sie nicht Teil der Vorlesung war.
In der Regel werden Sie in der Klausur (bei Anwendung von Algorithmen) den Zusatz “Benutzen Sie das Verfahren der Vorlesung” finden.

Das Verfahren der Vorlesung ist das Potenzmengenverfahren.
Dieses funktioniert auch für NFAs mit epsilon-Übergängen. Dazu müssen nur die Anweisungen in “2. Schritt” verwendet werden.

kurz zusammengefasst:

  • Sei NFA A=(Q,Sigma,delta,q0,F) gegeben.
  • Sei R eine Teilmenge von Q (die Zustände des NFA), dann entspricht E(R) der Menge der Zustände die bereits in R enthalten sind vereinigt mit den Zuständen, die mit (einem oder mehreren) epsilon-Übergängen von einem Zustand aus R erreicht werden können.
  • Die neue Zustandsmenge ist immer noch P(Q), die Potenzmenge von Q.
  • Der neue Startzustand ist dann E({q0}), also die Menge die den Startzustand und alle von dort aus mittels epsilon-Übergängen erreichbaren Zuständen enthält.
  • Die neue Menge von Endzuständen sind alle Teilmengen, die mind. einen Endzustand von A enthalten.
  • Die neue Übergangsfunktion delta’(R,a) ergibt sich durch die Vereinigung aller delta-Übergänge (delta(q,a)) von Zuständen q in R und davon muss man jeweils auch noch den epsilon-Abschluss E(delta(q,a)) nehmen.
1 „Gefällt mir“
4

Goto Betreff
Erstmal vielen Dank für die Antwort. Aber könnte ich Hieroglyphen lesen, hätte ich auch das Skript verstanden und mir keine Alternative Lösungsmethode gesucht. Ich habe das jetzt mal versucht für jedermann zugänglich zu formulieren:

  1. Ich bilde zuerst eine Potenzmenge der Zustände, wobei {} enthalten ist

  2. Ich forme den gegebenen Automaten so um, dass ich epsilon-Übergangszustände kombiniere (A -e-> B). D.h. {AB} wird der neue Zustand für A mit allen Kanten die A enthält + Selbereferenzkanten auf A für alle Kanten von B nach A. ( Wenn A hierbei ein Start / Endzustand ist, bleibt diese Eigenschaft erhalten )

  3. Der “neue” NEA wird zu einem DEA umgeformt.

Wenn ich das Verfahren aus der Vorlesung verwenden soll ( Was hoffentlich vorhergehendes ist ), an welchen Merkmalen wird festgesetzt, dass ich es verwendet habe? Ich meine, wenn ich eben nur den Graphen angebe, kann ja niemand nachvollziehen, wie ich darauf gekommen bin.

5

Nun ja - schade dass meine Antwort noch zu viele “Hieroglyphen” benutzt. Ich dachte es wäre hilfreich, zu den textuell erklärten Schritten die zugehörigen Symbole zu schreiben, damit man verstehen kann wofür die entsprechenden Symbole stehen.

Um den von mir beschriebenen Algorithmus zu benutzen muss man nur verstanden haben was eine Potenzmenge ist (ja die leere Menge ist darin enthalten) und wie ein Automat funktioniert.

Wenn nun für einige Ihre Formulierung “zugänglicher” ist freut mich das natürlich das wir diese nun hier verfügbar haben.

Fraglich bleibt nur wie der Schritt 3 bei Ihnen umzusetzen ist. Wenn man an dieser Stelle das Potenzmengenverfahren anwendet (und es verstanden hat) dann könnte man auch direkt das Potenzmengenverfahren anwenden, da der einzige Unterschied der ist, dass man statt der Zustandsmenge die man ohne epsilons hat immer die Zustände noch dazu nimmt, die mittels epsilon-Übergängen erreicht werden können - auch beim Startzustand (Hier nochmal in “Hieroglyphen”: statt Zustandsteilmenge R (Teilmenge von Q) nimmt man als Zustand im Potenzmengenautomaten immer E(R) ).

Ihr Schritt 2 ist wie bereits angedeutet nicht nach Vorlesung. Es kann jedoch sein, dass man mit Ihrer Vorverarbeitung auf den selben Potenzmengenautomaten kommt, wie mit dem Verfahren nach Vorlesung. In diesem Fall hätten Sie Glück und würden vermutlich trotzdem die Punkte bekommen. Um kenntlich zu machen, dass es das Verfahren der Vorlesung ist, müssen die Zustände des neuen Automaten Teilmengen der Zustände des ursprünglichen Automaten sein. Wenn ansonsten die Übergänge, Startzustand und Endzustände mit der korrekten Lösung übereinstimmen, so sollten Sie keine Probleme bekommen.

6

Könnten Sie Hieroglyphen lesen, sollten Sie Ägyptologie studieren. Kenntnis von Hieroglyphen ist beim Verständnis von Algorithmen und von mathematischen Formulierungen vermutlich keine Hilfe. Sorry, aber Ihre Bemerkung war nicht hilfreich.

Dies ist ein ungenauer, weil mißverständlicher (was heißt „{AB} wird der neue Zustand A“?) Versuch, den ε-Abschluß einer Zustandsmenge irgendwie in Worte zu fassen. Was die mathematische Beschreibung des Algorithmus der Vorlesung präzise und vollständig aussagt, ist: Bei Zustandmenge A, A ⊆ Q, und Eingabezeichen a ϵ Σ packe in δ(A,a) erst alle Zustände, die durch „einen `echten’ Schritt“ des NFA erreicht werden können. Danach packe noch alle Zustände hinzu, die durch ε-Übergangsfolgen erreicht werden können. Das habe ich so auch in der Vorlesung erklärt. Im übrigen ist der Startzustand des DFA der ε-Abschluß des Startzustands des NFA. Das bleibt bei Ihrer Beschreibung mindestens unklar.

Die Namen der Zustände in ihrem Graphen ergeben sich aus der Konstruktion und lassen erkennen, wie Sie sie ausgeführt haben.

BTW: NEA und DEA sind nicht die Bezeichnungen aus BFS.

7

[troll] In der Klausur dann so…

Minimieren Determinisieren Sie folgenden Automaten:

(Hinweis: dieser Automat wurde innerhalb von 2 Minuten gebaut und ist eventuell nicht so anwendbar)
[/troll]

3 „Gefällt mir“
8

Vielen Dank für die nette Erklärung, die hilft mir sehr weiter.

Das sollte humoristisch sein (Außenstehende verwendeten dies oft um mein Studium zu charakterisieren, nachdem sie erkannt haben das Info-Studium != Exel/Word Fortbildung ist) , hier konnte ich mir unter der rein mathematischen Beschreibung aus der Vorlesung nur leider nicht so viel vorstellen.

Vielen Dank auch an Alexander für die schnelle Antwort und die Erklärung. c: