NEA in DEA umwandeln |
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. |
17.03.2007, 21:09 | Auf diesen Beitrag antworten » |
Gisa | achsoooo jetzt wird es mir klar :-))))) Vielen vielen DANK :-) VG Gisa |
17.09.2007, 22:03 | Auf diesen Beitrag antworten » |
Gisa | Habe diese Aufgabe gefunden und beim Versuch sie zu lösen auf viele Schwierigkeiten gestoßen. Ich habe als folgenden Zustände für mein DEA erhalten nach der Anwendund der Potenzmengenkonstruktion: {q0q1q3}, {q0q1q2}, {q0q2q3}, {q0q2}, {q0q3} Waren zuviele Tranisitionen da a,b,c . Stimmen meine Zustände? Danke und grüße Gisa |
24.10.2007, 14:53 | Auf diesen Beitrag antworten » |
RedHead | Brauchst du noch ne antwort? |
24.10.2007, 17:16 | Auf diesen Beitrag antworten » |
Gisa | hat sich erledigt aber Danke :-) Viele Grüße Gisa |
30.01.2011, 22:41 | Auf diesen Beitrag antworten » |
dieAnna | hat sich erledigt. habs kapiert. |
30.01.2011, 22:44 | Auf diesen Beitrag antworten » |
dieAnna | "b: Mit b kommst du von 1 nach 2 aber auch von 2 nach 1. Also muss auch hier eine Schlaufe hin." ---> genau das check ich nicht. |
30.01.2011, 23:21 | Auf diesen Beitrag antworten » |
ed209 | Angenommen der Zustand ist im NEA ist entweder 1 oder 2 und es kommt ein b. Dann ist der Folgezustand im Falle einer 1 gleich 2 und im Falle einer 2 ist er gleich 1. Aus einem {1,2} wird also ein {2,1} was dasselbe ist. Methodisch gehst du so vor: Du nimmst bei einer Menge von Zuständen die möglichen Folgezustände von jedem Zustand und vereinst die. In deinem Fall: NFA (1,b) = {2} und NFA (2, b) = {1} und die Vereinigung von {2} und {1} ist {1,2} Ich bin mir nicht ganz sicher ob das deine Frage beantwortet. Jedoch denke ich daß in der Grafik ein Fehler ist: In dem DEA müsste {1,2} ein gültiger Endzustand sein. Davon ausgehend daß die dick umrandeten grünen Zustände Endzustände sind. Gruß, ED |
31.01.2011, 00:18 | Auf diesen Beitrag antworten » |
dieAnna | Oh mist, jetzt hab ich den beitrag gelöscht, weil ich nich gesehen hab, dass du geantwortet hast und es mir inzwischen klar wurde. vielen dank, trotzdem! Ach und ich hätt da noch ne andere Frage, zur Automatenminimalisierung: man stellt ja so eine Tabelle auf (siehe Schöning--> theoretische Informatik - kurzgefasst) in der alle zustandspaare auftauchen. dann markiert man all die paare, die nen endzustand enthalten. dann schaut man bei den restlichen nach, wo man landet, wenn man bei beiden (z.b.) ein a liest und checkt dann, ob die beiden zustände, in denen man landet bereits markiert sind. ist dies der fall, markiert man auch das zustandspaar, von dem man ausgegangen ist. meine frage: wenn mein alphabet aus a und b besteht. muss ich dann von jedem zustandspaar den "test" machen? Beispiel: Zu überprüfen: (q1-q2) Dann prüfe ich (q1, a) = ? und (q2, a) = ?? Und schau dann, ob (? - ??) bereits markiert ist. falls ja: markiere ich auch (q1 - q2). FALLS NEIN, versuche ich dasselbe mit "b" oder? LG, dieANNA |
31.01.2011, 00:47 | Auf diesen Beitrag antworten » |
ed209 | Wenn ich jetzt nichts vergessen habe: Zwei Zustände (q1 und q2) sind äquivalent, wenn für jede Eingabe x des Alphabets die Folgezustände f(q1,x) und f(q2,x) äquivalent sind und entweder q1 und q2 Endzustände oder q1 und q2 keine Endzustände sind. Gruß, ED (der jetzt langsam ins Bett muß) PS: Wenn ich mich recht entsinne macht man die minimierung normalerweise auf den deterministischen Automaten, wenn du da einen Zustand {q1,q2} hast, dann betrachte das als einen unabhängigen Zustand. (kannst den dann auch in q3 umbenennen, das ist wengier verwirrent). |
09.02.2011, 01:12 | Auf diesen Beitrag antworten » |
Gast | RE: NEA in DEA umwandeln Hi, also Pumping Lema besagt in meiner Kurzfassung, "es ist möglich an einer Stelle eines Wortes dieses Wort beliebig stark aufzublähen". Somit wenn du dir nochmals die deine Sprache anschaust, wirst du feststellen, dass an dieses realisierbar ist an denn, i≠j≠k und du kannst dein Wort ab der Stelle i bis zu Stelle k beliebig mit x^j aufblähen. |
10.02.2011, 16:11 | Auf diesen Beitrag antworten » |
Blackarro | Schade hab da auch noch eine Lösung gehabt |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|