0 Daumen
16 Aufrufe

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.

von

Bitte logge dich ein oder registriere dich, um die Frage zu beantworten.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...