Informatiker Board | Theoretische Informatik

Informatiker Board » Themengebiete » Theoretische Informatik » NEA in DEA umwandeln

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Seiten (2): [1] 2 nächste »

NEA in DEA umwandeln

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Gisa

Mitglied

Dabei seit: 06.02.2007
Beiträge: 47
Herkunft: DE

NEA in DEA umwandeln

Zitatantwort auf diesen Beitrag erstellen

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

__________________
"Imagination ist more than Knowledge"

12.03.2007 11:54

Nehmen Sie Gisa in Ihre Freundesliste auf

ed209
Routinier

Dabei seit: 07.09.2006
Beiträge: 324

Welchen Teil verstehst Du nicht?

12.03.2007 21:26

Nehmen Sie ed209 in Ihre Freundesliste auf

Gisa

Mitglied

Dabei seit: 06.02.2007
Beiträge: 47
Herkunft: DE

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

__________________
"Imagination ist more than Knowledge"

17.03.2007 18:21

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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

17.03.2007 18:28

Nehmen Sie Tobias in Ihre Freundesliste auf

Gisa

Mitglied

Dabei seit: 06.02.2007
Beiträge: 47
Herkunft: DE

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

__________________
"Imagination ist more than Knowledge"

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Gisa: 17.03.2007 19:42.

17.03.2007 19:40

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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 19:48

Gisa

Mitglied

Dabei seit: 06.02.2007
Beiträge: 47
Herkunft: DE

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

__________________
"Imagination ist more than Knowledge"

17.03.2007 20:07

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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:12

Gisa

Mitglied

Dabei seit: 06.02.2007
Beiträge: 47
Herkunft: DE

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

__________________
"Imagination ist more than Knowledge"

17.03.2007 20:31

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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 20:51

Gisa

Mitglied

Dabei seit: 06.02.2007
Beiträge: 47
Herkunft: DE

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

VG
Gisa

__________________
"Imagination ist more than Knowledge"

17.03.2007 21:09

Gisa

Mitglied

Dabei seit: 06.02.2007
Beiträge: 47
Herkunft: DE

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

__________________
"Imagination ist more than Knowledge"

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Gisa: 17.09.2007 22:05.

17.09.2007 22:03