Hallo ich habe Probleme beim Verstehen der Rechtskongruenzrelation.
Definitionen:
1)
Sei L ∈ Σ*, x,y ∈ Σ* heißen Äquivalent bzgl. L (x ≈ y), falls gilt:
∀ z ∈ Σ* xz ∈ L ⇔ yz ∈ L
(≈ heißt auch Rechtskongruenzrelation)
2)
Sei M ein DEA über Σ*. Zwei Wörter x,y ∈ Σ* heißen äquivalent bzgl. M (x ~ y), wenn gilt:
∃q ∈ K mit (s,x) |− (q,λ) und (s,y) |− (q,λ)
(in Worten: M erreicht bei Anwendung der gleichen Rechnung auf x und y denselben Zustand)
≈ und ~ sind Äquivalenzrelationen auf Σ* und aus x ~ y folgt x ≈ y.
--------------------------------------------------------------------------------------------------
Nun habe ich z.B. zwei unterschiedliche Automaten, die von der selben Sprache beschrieben werden.
L(M1) = {w ∈{a,b}* | die Anzahl der b(w) ist gerade}; (M1 hat 4 Zustände, davon 2 Endzustände)
L(M2) ={w ∈{a,b}* | die Anzahl der b(w) ist gerade}; (M2 hat 2 Zustände, davon 1 Endzustand)
Die Automaten kann ich ohne Probleme zeichnen.
Nun wurde aber gesagt, dass
L(M2) = L(M1)
≈ L(M2) = ≈ L(M1)
~ M2 ⊇ ~ M1
~ M2 = ≈ L(M2)
~ M1 ⊆ ≈ L(M1)
L(M2) = L(M1) ist klar.
Aber warum stehen die anderen in dieser Beziehung und wie sehen ≈ L(M2) ; ≈ L(M1) ; ~ M1 ; ~ M2 überhaupt aus? Kann man das als eine Art Menge sehen, wie sieht der Inhalt aus, das muss man ja irgendwie erkennen können, damit man diese Aussagen über die Beziehungen treffen kann?
Danke im Vorraus.
