Relación de equivalencia de lenguajes

Para cada lenguaje $L\subset \mbox{$\Sigma^*$}$ podemos construir una relación de equivalencia sobre $\mbox{$\Sigma^*$}$:

$$xR_Ly \Longleftrightarrow (\forall z\in\mbox{$\Sigma^*$}: xz\in L \Longleftrightarrow yz\in L)$$

es decir, $x$ es equivalente a $y$, si, añadiendo cualquier sufijo, ambas palabras resultantes o bien están en $L$ o bien no están en $L$.

Observa: $z=\epsilon: x\in L \Longleftrightarrow y\in L$, es decir, o bien todas las palabras de una clase están en $L$ o bien ninguna palabra de una clase está en $L$.

Ejercicio:¡Verifica que $R_L$ es una relación de equivalencia!