---

Geschrieben von Gisa am 12.03.2007 um 11:54:

  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

---

Geschrieben von ed209 am 12.03.2007 um 21:26:

 

Welchen Teil verstehst Du nicht?

---

Geschrieben von Gisa am 17.03.2007 um 18:21:

 

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

---

Geschrieben von Tobias am 17.03.2007 um 18:28:

 

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

---

Geschrieben von Gisa am 17.03.2007 um 19:40:

 

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

---

Geschrieben von Tobias am 17.03.2007 um 19:48:

 

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}

---

Geschrieben von Gisa am 17.03.2007 um 20:07:

 

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

---

Geschrieben von Tobias am 17.03.2007 um 20:12:

 

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.

---

Geschrieben von Gisa am 17.03.2007 um 20:31:

 

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

---

Geschrieben von Tobias am 17.03.2007 um 20:51:

 

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.

---

Geschrieben von Gisa am 17.03.2007 um 21:09:

 

achsoooo jetzt wird es mir klar :-)))))
Vielen vielen DANK :-)

VG
Gisa

---

Geschrieben von Gisa am 17.09.2007 um 22:03:

 

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

---

Geschrieben von RedHead am 24.10.2007 um 14:53:

 

Brauchst du noch ne antwort?

---

Geschrieben von Gisa am 24.10.2007 um 17:16:

 

hat sich erledigt aber Danke :-)

Viele Grüße
Gisa

---

Geschrieben von dieAnna am 30.01.2011 um 22:41:

 

hat sich erledigt. habs kapiert.