Myhill-Nerode

riz_ · Newbie Anmeldungsdatum: 17.05.2012 Beiträge: 1

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