Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Myhill-Nerode
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> Myhill-Nerode
 
Autor Nachricht
riz_
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 17.05.2012
Beiträge: 1

BeitragVerfasst am: 17 Mai 2012 - 20:10:47    Titel: Myhill-Nerode

Hallo!
Ich habe eine Aufgabe und komme nicht ganz klar:
Bestimmen Sie die Aquivalenzklassen der Myhill-Nerode-Relation für die folgenden Sprachen. Geben Sie den Minimalautomaten an, falls es sich um eine reguläre Sprache handelt. Begründen Sie Ihre Antworten.
L1 = {w element von {0,1}* | die Anzahl der 0en und 1en in jedem Präfix von  w unterscheidet sich um hochstens 1}

Ich suche also die Äquivalenzklassen. Wenn es endlich viele gibt, ist L1 regulär. Habe die folgenden gewählt:
K0 = {|1| = |0|-2} (es gibt 2 0en weniger als 1en) -> muss eine 1 anhängen
K1 = {|0| = |1|-2} (es gibt 2 1en weniger als 0ed) -> muss eine 0 anhängen
Kg = {|1| = |0|} -> kann eine 1 oder 0 anhängen.
Stimmt das so? Daraus würde folgen dass L1 regulär ist, also gibt es einen Minimalautomaten dazu. Wie würde ich den jetzt konstruieren?

Ein anderer Ansatz wäre zu sagen, dass ich unendlich viele ÄKs bilden kann, z.B. 2 0en weniger als 1en -> muss 0 anhängen.
3 0en weniger als 1en -> muss 2 0en anhängen.
4 0en weniger als 1en -> muss 3 0en anhängen.
usw.
Ich bin leicht verwirrt - welcher Ansatz ist der richtige?
Danke schonmal recht herzlich
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> Myhill-Nerode
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum