| Die letzten 5 Beiträge |
| Karlito |
Ich gehe davon aus dass dies hier ein Doppelpost ist.
NEA mit nur einem Endzustand erkennt jede Sprache?
sapere aude |
| 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? |
| RA-KI |
Ja das klingt einleuchtend und wenn man es einmal weiß auch sehr einfach. =)
Vielen Dank. |
| 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 |
| 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. |
|
|
