NEA in DEA umwandeln

Neue Frage »

12.03.2007, 11:54	Auf diesen Beitrag antworten »
Gisa	NEA in DEA umwandeln Hallo Forum, ich weiss nicht genau wie man einen NEA in einen DEA umwandelt. Bräuchte dazu beispielen und Informatiionen. Bei Wikipedia z.B. ist es ziemlich schlecht erklärt. Vielen Dank im Voraus. Grüße Gisa


12.03.2007, 21:26	Auf diesen Beitrag antworten »
ed209	Welchen Teil verstehst Du nicht?
17.03.2007, 18:21	Auf diesen Beitrag antworten »
Gisa	also wie man im DEA die "neuen" Zustände bekommt. Wenn aus einem NEA AUtomaten ein DEA Automat entsteht. Dann enstehen meist neue gemixte Zustände. Siehe hierzu Link. Meine Frage ist: Wie kommt man zu den neuen Zuständen? Nach welchem Muster geht man da? Danke und Grüße Gisa
17.03.2007, 18:28	Auf diesen Beitrag antworten »
Tobias	Du beginnst bei Zustand 1 und betrachtest jetzt nacheinander die Transitionen: a: Von 1 kommt man mit a nach 1 und 2. Also konstruierst du einen neuen Zustand {1, 2} und malst eine a-Transition von 1 nach {1, 2}. Weil in {1, 2} ein Zustand vorkommt, der Endzustand ist, ist {1, 2} auch Endzustand. b: Von 1 kommst du nur nach 2, also erzeugst du Zustand 2. Jetzt gehts weiter mit Zustand {1, 2}: a: Mit a kommst du von 1 nach 1 und 2, also malst du eine a-Schlaufe. b: Mit b kommst du von 1 nach 2 aber auch von 2 nach 1. Also muss auch hier eine Schlaufe hin. usw. Zuletzt brauchst du noch eine Senke, zu der alle Transitionen führen, die in dem NEA nicht existieren. Das Ganze heißt Potenzmengenkonstruktion http://de.wikipedia.org/wiki/Potenzmengenkonstruktion
Anzeige

17.03.2007, 19:40	Auf diesen Beitrag antworten »
Gisa	Alles klar. Gut das ist soweit verstanden. Also ich kann mit a sowohl in 1 als auch in den 2 Zustand übergehen und habe deswegen den neuen Zustand {1 2} Gut soweit ist das klar. Vielen Dank. Auf dieses Beispiel unten kann ich die obige Methode nicht anwenden. VOn 1 aus gelande ich mit a zuerst in 3 dann weiterhin mit a in 2 und anschließend in 1- Also erzeuge ich als erstes den Zustand {1 2 3}. Dann von der 3 aus mit b einmal erneut zu sich selbst und zu 2 also habe ich dann den Zustand {2 3}. Woraus bekomme ich den Zustand {1 2} her? Danke und viele Grüße Gisa
17.03.2007, 19:48	Auf diesen Beitrag antworten »
Tobias	Vom Zustand {2, 3} kommst du mit a von 2 nach 1 von 2 nach 2 und von 3 nach 2. Also {2, 3} --- a ----> {1, 2}
17.03.2007, 20:07	Auf diesen Beitrag antworten »
Gisa	Oh Mann! Ich verstehe diese Abfolge nicht. Du orientierst dich doch an dem NEA oder? Also den Zustand 123 erhalten ich ja, weil ich mit a in einem Sprung quasi in alle Zustände gelange. 12 geht ja nicht da es ja auch nach 3 geht mit einem a. Deswegen bekomme ich keinen Zustand 12. Wo mache ich meinen Denkfehler? Grüße gisa
17.03.2007, 20:12	Auf diesen Beitrag antworten »
Tobias	Du orientierst dich am Startzustand des NEA. Der ist auch Startzustand im DEA. Dann betrachtest du vom Startzustand alle möglichen Transitionen im NEA in Folgezustände, die z.T. auch aus mehreren Zuständen zusammengesetzt sein kann, wie z.B. {1, 2, 3}. Jetzt gehst du von einem neuen Zustand im DEA weiter, z.B. {1, 2, 3}. Von diesem Zustand guckst du dir wieder alle möglichen Transitionen an, indem du dir im NEA die Transitionen aller Elemente aus {1, 2, 3} anschaust usw.
17.03.2007, 20:31	Auf diesen Beitrag antworten »
Gisa	Also ich schaue mir von dem neuen Zustand {123} alle möglichen Transitionen im NEA an an. Ist es etwa so gemeint, dass der neue Zustand ja schon alle Zustände beinhaltet und deswegen auch 1 und 2 ein neuer Folgezustand ist? Sorry :-) Grüße Gisa
17.03.2007, 20:51	Auf diesen Beitrag antworten »
Tobias	Nein, der Folgezustand {1,2} entsteht, wenn du dir die Folgezustände von {2,3} anschaust. Du musst ir grundsätzlich zu jedem Zustand, den du im DEA erzeugst alle Folgezustände betrachten.

nächste Seite

Neue Frage »

Antworten »

NEA in DEA umwandeln

Verwandte Themen