---

Geschrieben von RA-KI am 24.11.2011 um 17:49:

  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.

---

Geschrieben von Karlito am 24.11.2011 um 18:14:

 

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

---

Geschrieben von RA-KI am 24.11.2011 um 18:46:

 

Ja das klingt einleuchtend und wenn man es einmal weiß auch sehr einfach. =)
Vielen Dank.

---

Geschrieben von RA-KI am 25.11.2011 um 14:21:

 

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?

---

Geschrieben von Karlito am 25.11.2011 um 20:25:

 

Ich gehe davon aus dass dies hier ein Doppelpost ist.

NEA mit nur einem Endzustand erkennt jede Sprache?

sapere aude