Die Nerode-Kongruenz (I)

Für jede Sprache L $\subseteq$ $\Sigma^{*}_{}$ definieren wir eine Äquivalenzrelation auf $\Sigma^{*}_{}$ durch

u $\displaystyle \sim_{L}^{}$ v : $\displaystyle \iff$ $\displaystyle \forall$ w $\displaystyle \in$ $\displaystyle \Sigma^{*}_{}$ : (uw $\displaystyle \in$ L $\displaystyle \iff$ vw $\displaystyle \in$ L)

Beispiele: $\Sigma$ = {a, b}, L₁ = a^*b^*, L₂ = {aⁿbⁿ | n $\ge$ 0}.

Welche der Wörter sind jeweilskongurent:

$\displaystyle \epsilon$ , a, b, ab, ba, a⁴, a⁴b⁴?

Wieviele Kongruenzklassen gibt es?

Johannes Waldmann 2008-01-24