Informatiker Board | Theoretische Informatik | NEA mit höchstens zwei Endzuständen?

Informatiker Board » Themengebiete » Theoretische Informatik » NEA mit höchstens zwei Endzuständen?

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

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

NEA mit höchstens zwei Endzuständen?

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

RA-KI
Grünschnabel

Dabei seit: 24.11.2011
Beiträge: 3

NEA mit höchstens zwei Endzuständen?

Zitatantwort auf diesen Beitrag erstellen

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 17:49

Nehmen Sie RA-KI in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Karlito: 24.11.2011 18:19.

24.11.2011 18:14

Nehmen Sie Karlito in Ihre Freundesliste auf

RA-KI
Grünschnabel

Dabei seit: 24.11.2011
Beiträge: 3

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

24.11.2011 18:46

RA-KI
Grünschnabel

Dabei seit: 24.11.2011
Beiträge: 3

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?

25.11.2011 14:21

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Ich gehe davon aus dass dies hier ein Doppelpost ist.

NEA mit nur einem Endzustand erkennt jede Sprache?

sapere aude

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Karlito: 25.11.2011 20:28.

25.11.2011 20:25

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » NEA mit höchstens zwei Endzuständen?