\begin{slide}{Die Nerode-Kongruenz (I)}

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

\[ u \sim_L v :\iff \forall w\in\Sigma^*: (uw \in L \iff vw \in L) \]

Beispiele:
$\Sigma=\{a,b\},L_1=a^*b^*, L_2=\{a^nb^n \mid n\ge 0\}$. 

Welche der Wörter sind jeweilskongurent:

\[\epsilon,a, b, ab, ba, a^4, a^4b^4? \]

Wieviele Kongruenzklassen gibt es?


\end{slide}

\begin{slide}{Die Nerode-Kongruenz (II)}

Satz: Für jede Sprache $L\subseteq\Sigma^*$:
 
$L$ ist regulär $\iff$ $\Sigma^*/\sim_L$ ist endlich
($\sim_L$ besitzt endlich viele Äquivalenzklassen).

Beweis: die Äquivalenzklassen von $\sim_L$
sind die Zustände eines minimalen deterministischen vollständigen
Automaten für $L$.


\end{slide}
