NEA in DEA umwandeln |
Gisa
Mitglied
Dabei seit: 06.02.2007
Beiträge: 47
Herkunft: DE
|
|
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 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
Welchen Teil verstehst Du nicht?
|
|
12.03.2007 21:26 |
|
|
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 |
|
|
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 |
|
|
RedHead
Grünschnabel
Dabei seit: 17.03.2007
Beiträge: 7
|
|
Brauchst du noch ne antwort?
|
|
24.10.2007 14:53 |
|
|
Gisa
Mitglied
Dabei seit: 06.02.2007
Beiträge: 47
Herkunft: DE
|
|
hat sich erledigt aber Danke :-)
Viele Grüße
Gisa
__________________ "Imagination ist more than Knowledge"
|
|
24.10.2007 17:16 |
|
|
|