Äquivalenzrelationen von Sprache auf Alphabet

Question

(1)

Sei Σ = {a, b, c} ein Alphabet. Wir betrachten die folgende Sprache L ⊆ Σ∗:
L = {w ∈ Σ∗ | w beginnt und endet mit einem a}
Bezüglich L definieren wir die Äquivalenzrelation ∼L auf Σ∗ durch
u ∼L v falls für alle z ∈ Σ∗ gilt: uz ∈ L genau dann, wenn vz ∈ L
Geben Sie alle 4 Äquivalenzklassen von ∼L an


(1) Frage: Was wären in diesem Fall die 4 Äquivalenzrelationen? Und was ist eine gute Herangehensweise für diesen Typ von Aufgabe generell?

(2)

Sei Σ = {a, b, c} ein Alphabet. Wir betrachten die folgende Sprache L ⊆ Σ∗:
L = {w ∈ Σ∗ | w beginnt mit ab und endet mit bb}
Bezüglich L definieren wir die Äquivalenzrelation ∼L auf Σ∗ durch
u ∼L v falls für alle z ∈ Σ∗ gilt: uz ∈ L genau dann, wenn vz ∈ L
Bestimmen Sie alle 6 Äquivalenzklassen von ∼L : Geben Sie hierfür jeweils einen kürzesten Repräsentanten an und
beschreiben Sie die Äquivalenzklasse in natürlicher Sprache

(2) Frage: Auch hier analog, was wären die 6 Äquivalenzklassen

Danke!

Answer 1

Prüfe kurze Worte.

Das Wort a liegt in einer Äquivalenzklasse.

Liegt das Wort b in der gleichen Äquivalenzklasse wie das Wort a?

Liegt das Wort c in der gleichen Äquivalenzklasse wie das Wort a oder wie das Wort b?

Wie sieht es mit dem Wort aa aus?

Und so weiter.

Comments

Könnten Sie beim ersten Beispiel konkret die 4 Äquivalenzklassen nennen? Ich komme leider noch nicht darauf.