0 Daumen
2,1k Aufrufe

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!

Avatar von

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.

1 Antwort

0 Daumen
 
Beste Antwort

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.

Avatar von 5,6 k

Super, das hilft mir enorm!

Vielen lieben Dank :)

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community