Myhill-Nerode-Relation, Äquivalenzklassen

Question

Betrachten Sie die Sprache L = {01, 1, 10, 001, 0011} ⊆ {0, 1}∗
.
(a) Geben Sie ein z ∈ {0, 1}∗ an, für das 1z ∈ L aber 001z ∉ L gelten.
(b) Geben Sie ein z ∈ {0, 1}∗ an, für das 10z ∈ L und 001z ∈ L gelten.
(c) Betrachten Sie die beiden Myhill-Nerode Äquivalenzklassen [01] und [1]. Zeigen Sie,
dass [01] ≠ [1] gilt.
(d) Zeigen Sie, warum die Anzahl der paarweise verschiedenen Myhill-Nerode Äquivalenzklassen
endlich ist.

Comments

Bitte Poste die einzelnen Aufgabenteile jeweils als eigenständige Frage mit sinnvollen Fragentiteln (die (a) kannst Du hier stehen lassen; (b) bis (d) bitte separat).

Was hast Du bereits selbst versucht?

Answer 1

Betrachten Sie die Sprache L = {01, 1, 10, 001, 0011} ⊆ {0, 1}∗
.
(a) Geben Sie ein z ∈ {0, 1}∗ an, für das 1z ∈ L aber 001z ∉ L gelten.

Ich verstehe André so:

1. Nimm z=1 ,

2. Schaue, ob 11 in L vorkommt. --> nein.

Somit kann z=1 nicht die Lösung von (a) sein.

Neuer Versuch: 

1. Nimm z=0 ,

2. Schaue, ob 10 in L vorkommt. --> ja.

3. Schaue, ob 0010 in L vorkommt. ---> nein.

Somit passt z=0 als Antwort zur Frage (a) . Du bist fertig.