Definition
Für eine \(L \subseteq \varSigma^*\) definieren wir:
\[u \simeq v :\Longleftrightarrow \forall w \in \varSigma^*: u w \in L \Longleftrightarrow v w \in L\]
Beweis, dass \(\simeq\) eine Äquivalenzrelation und \([u]_L\) eine Äquivalenzklasse ist
Beispiel:
\[\begin{split}&L = \{ w \in \{0,1\}^* \mid \text{w endet mit 00} \} \\
&\varepsilon \simeq 1, \text{ denn } w \in L \Longleftrightarrow 1w \in L \\
&\varepsilon \not\simeq 0, \text{ denn } 0 = \varepsilon 0 \notin L, 00 \in L\\
&\varepsilon \simeq 11, \text{ denn } 1w \in L \Longleftrightarrow 11w \in L \\
&\varepsilon \simeq u1, \text{ denn } 1w \in L \Longleftrightarrow u1w \in L \\
&\varepsilon \not\simeq 00, \text{ denn } 0 \varepsilon \in L \text{ und } 00 \varepsilon = 00 \in L \\
&\varepsilon \simeq 10, \text{ denn } 0w \in L \Longleftrightarrow 10w \in L \\
&\varepsilon \simeq u10, \text{zweite und dritte Äquivalenzklasse}\end{split}\]
zweite Äquivalenzklasse: \([0] = \{ w \mid \text{w endet mit 0, aber nicht mit 00} \}\)
dritte Äquivalenzklasse: \([00] = \{ w \mid \text{w endet mit 00} \}\)
3 Äquivalenzklassen: \(\varSigma^* = [\varepsilon] \cup [0] \cup [00]\)