NEA mit höchstens zwei Endzuständen? |
| 24.11.2011, 17:49 | Auf diesen Beitrag antworten » |
| RA-KI | NEA mit höchstens zwei Endzuständen? Meine Frage: Kann man jeden beliebigen NEA, ohne Wortübergängen, in einen äquivalenten NEA mit höchstens zwei Endzuständen umwandeln? Angeblich schon. Aber wie begründet, beweist man das? Meine Ideen: Da Wortübergänge und Epsilon-Übergänge nicht erlaubt sind, fehlt mir leider jeglicher Ansatz. |
|
|
|
| 24.11.2011, 18:14 | Auf diesen Beitrag antworten » |
| Karlito | Hi, wie du vlt weißt, kann man zu jedem NEA mit einem epsilon-Übergang effektiv einen äquivalenten NEA ohne epsilon-Übergang konstruieren. Für Sprachen, die das leere Wort nicht enthalten: 1. Wenn du nun den NEA ohne epsilon- und Wortlübergänge hast, führe einen neuen Zielzustand ein. 2. Danach erstelle von jedem deiner alten Zielzustände einen epsilon-Übergang auf den neuen Zielzustand. 3. Streiche alle Zielzustände, bis auf den neu erstellten Zielzustand, aus der Menge der Zielzustände. 4. Konstruiere einen äquivalenten NEA ohne epsilon-Übergänge. Sollte deine Sprache das leere Wort akzeptieren, dann ist zusätzlich noch dein Startzustand ein Finalzustand. Somit kommst du mit max. 2 FInalzuständen hin. Wenn ich mich nicht irre bis du damit fertig. VG, Karlito |
| 24.11.2011, 18:46 | Auf diesen Beitrag antworten » |
| RA-KI | Ja das klingt einleuchtend und wenn man es einmal weiß auch sehr einfach. =) Vielen Dank. |
| 25.11.2011, 14:21 | Auf diesen Beitrag antworten » |
| RA-KI | Mir kommt grade der Gedanke: Wenn ich jetzt aus dem Epsilon-NEA, der nur zwei Endzustände hat, einen normalen NEA mache. Ist denn in jedem Fall die Anzahl der Endzustände gleich? |
| Anzeige | |
|
|
|
| 25.11.2011, 20:25 | Auf diesen Beitrag antworten » |
| Karlito | Ich gehe davon aus dass dies hier ein Doppelpost ist. NEA mit nur einem Endzustand erkennt jede Sprache? sapere aude |
|
|
