Nerode-Relation Äquivalenzklassen der Sprache L= {0,1,01}

Question

Hallo Community,

ich habe eine Frage zu folgender Aufgabe:

" Bestimmen Sie die Menge Σ∗/∼ L der Äquivalenzklassen der Sprache L={0,1,01} über dem Alphabet Σ={0,1} und konstruieren Sie den Äquivalenzklassenautomaten (‘Nerode-Automat’)"

Ich habe das Bestimmen der Klassen glaube ich noch nicht richtig verstanden - wären das nicht einfach folgende 4 Klassen?:

[ɛ]

[0]

[1]

[01]

Vielen Dank im Voraus!

Comments

In welcher Klasse ist das Wort 010, 0100, 0101, 01000, ... ?

---

Diese Wörter sollten doch gar nicht berücksichtigt werden oder

---

Doch, wie du in Oswald's Antwort auch sehen kannst.

Answer 1

Das Wort 01 kann nur durch das leere Wort zu einem Wort aus L ergänzt werden. Ich packe es in die Äquivalenzklasse [01].

Das Wort 1 kann nur durch das leere Wort zu einem Wort aus L ergänzt werden. es gehört also auch in die Äquivalenzklasse [01].

Das Wort 0 kann nicht nur durch das leere Wort, sondern auch durch 1 zu einem Wort aus L ergänzt werden. Es gehört deshalb nicht die Äquivalenzklasse [01], sondern in die Äquivalenzklasse [0].

Dass leere Wort ɛ kann durch 0, 1, und 01 zu einem Wort aus L ergänzt werden. Es gehört deshalb in die Äquivalenzklasse [ɛ].

Alle anderen Wörter (z.B. 10) können nicht zu einem Wort aus L ergänzt werden. Sie gehören in die Äquivalenzklasse [10].

Diese Wörter sollten doch gar nicht berücksichtigt werden oder

Die Nerode-Relation teilt \(\Sigma^*\) in Äquivalenzklassen ein. Jedes Wort aus \(\Sigma^*\) landet in einer Äquivalenzklasse.

Comments

Super, das hilft mir enorm!

Vielen lieben Dank :)