Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Äquivalenzklassen der Nerode-Relation

Äquivalenzklassen der Nerode-Relation

Universität / Fachhochschule

Tags: Äquivalenzklassen, Nerode-Relation, Relation.

Stuudent aktiv_icon

16:33 Uhr, 07.11.2019

Sei

Σ = {0, 1}

und bezeichne

{| w |}_{0}

die Anzahl des Buchstabens

0

in einem Wort

w \in Σ^{⋆}

sowie

{| w |}_{1}

die Anzahl des Buchstabens 1. Weiterhin seien:

K_{g, g} = {w | w \in Σ^{⋆}

mit

{| w |}_{0} \equiv 0 mod 2 \land {| w |}_{1} \equiv 0 mod 2}

K_{u, g} = {w | w \in Σ^{⋆}

mit

{| w |}_{0} \equiv 1 mod 2 \land {| w |}_{1} \equiv 0 mod 2}

K_{u, u} = {w | w \in Σ^{⋆}

mit

{| w |}_{0} \equiv 1 mod 2 \land {| w |}_{1} \equiv 1 mod 2}

K_{g, u} = {w | w \in Σ^{⋆}

mit

{| w |}_{0} \equiv 0 mod 2 \land {| w |}_{1} \equiv 1 mod 2}

Die Sprache

L

sei die Menge

K_{g, g}

. Nun soll ich zeigen, dass die Mengen

K_{g, g}, K_{u, g}, K_{u, u}

und

K_{g, u}

die Äquivalenzklassen von

Σ^{⋆}

bezüglich der Nerode-Relation

R_{L}

ist.

Die Nerode-Relation ist wie folgt definiert:
für

x, y \in Σ^{⋆}

gilt

x R_{L} y \Leftrightarrow (x \cdot z \in L \Leftrightarrow y \cdot z \in L)

Leider habe ich keine Idee, wie ich an die Aufgabe herangehen kann? Über Hilfestellungen würde ich mich sehr freuen!

Gruß, Niko

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."