2 votos

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

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$ ?

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$

3voto

SpectreWriter Puntos 609

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

De hecho, ¿por qué no podríamos haber escrito la última clase? $c\Sigma^*+a\Sigma^++b(a+c)\Sigma^*+bb\Sigma^*(b+c)\Sigma^*$ como $4$ ¿clases de equivalencia separadas?

1 votos

@Yos Porque la relación especifica que dos elementos están en la misma clase de equivalencia si y sólo si para todos $z\in \Sigma^*$ o bien $xz$ y $yz$ son ambos aceptados o ambos rechazados. Considere las cadenas $c$ y $a$ . ¿Puedes encontrar un $z$ tal que $cz$ se acepta pero $az$ no es o viceversa? Si no puede, entonces deben estar en la misma clase de equivalencia.

0 votos

Por lo que si la clase eq. tuviera $c\Sigma^*+a\Sigma^*$ podríamos haber dividido la clase en dos, ¿verdad? porque $c\epsilon\notin L$ pero $a\epsilon\in L$

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X