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}, L1 = a*b*, L2 = {anbn | n$ \ge$0}.

Welche der Wörter sind jeweilskongurent:

$\displaystyle \epsilon$, a, b, ab, ba, a4, a4b4?

Wieviele Kongruenzklassen gibt es?



Johannes Waldmann 2008-01-24