Es fácil demostrar que las clases de equivalencia de Nerode son las mismas para un lenguaje $L$ y su complemento $L'$ . $$ xR_Ly \iff \left(\forall z\in \sum^*:xz\in L \iff yz \in L\right) \\ xR_{L'}y \iff \left(\forall z\in \sum^*:xz\in L' \iff yz \in L'\right) $$ Dado que las cadenas en $L'$ son exactamente las cadenas que no están en $L$ entonces $$ xz\in L \iff xz\not\in L' \\ \left(xz\in L \iff yz \in L\right) \iff \left(xz\not\in L' \iff yz \not\in L'\right) \iff \left(xz\in L' \iff yz \in L'\right) $$ Por lo tanto, $$ \left(\forall z\in \sum^*:xz\in L \iff yz \in L\right) \iff \left(\forall z\in \sum^*:xz\in L' \iff yz \in L'\right) \\ xR_Ly \iff xR_{L'}y $$
Parece que has olvidado las clases de equivalencias que contienen todas las cadenas que no son aceptadas. Sin embargo, le advierto que no intente encontrar las clases de equivalencia de la forma en que lo ha hecho.
Una de las razones es que puede haber múltiples clases de equivalencia de cadenas que no se aceptan (por ejemplo, esta pregunta ). No siempre serán evidentes y es posible que no pueda adivinarlos a partir de la definición.
Otra razón es que las clases de equivalencia de aceptación que se leen pueden no ser clases de equivalencia separadas. Por ejemplo, ¿qué pasaría si cambiáramos un poco su lenguaje: el lenguaje generado por $\{\epsilon,a,b,bba^*,aba^*\}$ . También se puede afirmar que las clases de equivalencia que se aceptan son $$ S_1=\{\epsilon\} \\ S_2=\{a\} \\ S_3=\{b\} \\ S_4=\{bba^*\} \\ S_5=\{aba^*\} \\ $$ Sin embargo, esto no es cierto. Las cadenas $a$ y $b$ deben estar en la misma clase de equivalencia, ya que no pueden estar separadas por ninguna $z\in\Sigma^*$ .
Por estas razones, me gustaría altamente recomiendan encontrar el DFA mínimo de un lenguaje para encontrar las clases de equivalencia. Tu manera funcionó (aunque te faltó la última clase de equivalencia), pero para muchos otros lenguajes te dará una respuesta muy equivocada.
0 votos
Creo que debemos interpretar $R_L = R_{L'}$ como "hay una biyección (posiblemente incluso un isomorfismo, no sé el teorema al que te refieres) entre $R_L$ y $R_{L'}$ "en lugar de una igualdad literal, porque digamos que $L = \{\varepsilon\}$ entonces $R_L = \{\{\varepsilon\}\}$ pero $R_{L'} = \{\Sigma \Sigma^*\}$ ¿verdad?
0 votos
$R_L=R_L'$ significa que $R_L$ y $R_L'$ tienen las mismas clases de equivalencia.
1 votos
En realidad ahora tiene sentido para mí por qué la quinta clase eq. está en $R_L$ porque necesitamos una clase para todas las palabras que no están en $L$ por lo que para cualquier $z\in\sum^*: xz\notin L\iff xy\notin L$ Así que $xR_Ly$
0 votos
Sí, yo también lo creo.