¿Cómo encontrar las clases de equivalencia de un complemento de lenguaje formal?

Question

Dejemos que $L=\{\sum^*-(\{\epsilon, a,b\}\cup \{bba^i|i\ge 0\})\}$ sea una lengua sobre $\sum=\{a,b,c\}$ . Encuentre las clases de equivalencia de la relación $R_L$ que se define como sigue: $xR_Ly \iff \forall z\in \sum^*:xz\in L \iff yz \in L$ .

Hemos aprendido un teorema que $R_L=R_{L'}$ donde $L'$ es el complemento de $L$ . Así que para encontrar $R_L$ de $\{\sum^*-(\{\epsilon, a,b\}\cup \{bba^i|i\ge 0\})\}$ equivale a encontrar $\{\epsilon, a,b\}\cup \{bba^i|i\ge 0\}$ .

$\{\epsilon, a,b\}\cup \{bba^i|i\ge 0\}=\{\epsilon, a,b,bba^*\}$ . Así que hay $4$ clases de equivalencia: $$S_1=\epsilon\\ S_2=a\\S_2=b\\S=bba^*$$ .

Sin embargo, la solución a este problema menciona la quinta clase: $$c\Sigma^*+a\Sigma^++b(a+c)\Sigma^*+bb\Sigma^*(b+c)\Sigma^*$$ No entiendo lo que representa esta clase. Parece que en realidad representa las palabras en $L'$ . Pero si es así por qué lo añadimos ya que estas palabras no están en $L$ ?

Answer 1

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.