Myhill Nerode - ¿lengua regular o no?

Question

Estoy tratando de entender cómo encontrar clases de equivalencia de un lenguaje para demostrar su regularidad. Creo que si soy capaz de entender COMPLETAMENTE un ejemplo entonces entenderé bien este tema.

Digamos que tengo un idioma

$L=\{a^{m} b^{n} :1\le m \le n\}$ sobre el alfabeto $\Sigma=\{a,b\}$

Mi enfoque es el siguiente:

$K_{\epsilon} = \{\epsilon\}$ - que contiene una palabra vacía. Si concatenamos cualquier palabra $z$ de la lengua, entonces la palabra de esta clase estará en la lengua.

$K_{A} = \{a^{i}\} \land i \gt 1$ - que contiene cadenas de a's. Si concatenamos la palabra $z = b^{k} \land k>i$ que todas las cadenas de esta clase estarán en el idioma. Hay infinitas clases de este tipo.

$K_{AB} = \{a^{i}b^{j}\} \land i>1 \land j<i$ - que contiene cadenas de a's y b's. Si concatenamos la palabra $z=b^{i-j+1}$ entonces las palabras de esta clase estarán en la lengua. Hay infinitas clases de este tipo.

Lo que no entiendo es por qué estamos buscando esa palabra $z$ y por qué una longitud de palabra diferente constituye una nueva clase. También ¿por qué las palabras de las clases no tienen que ser incluidas en el lenguaje?

Sé que todavía tengo que demostrar que esas clases no están relacionadas pero primero quiero entender lo de arriba.

Por favor, dame una intuición más que una solución - quiero entenderlo más que hacerlo :)

Answer 1

La relación Myhill-Nerode $\equiv_L$ de $L$ es una relación sobre $\Sigma^*$ (no en $L$ por lo que los representantes no tienen que ser miembros de $L$ como ha observado). Es por las palabras $x,y \in \Sigma^*$ definido por $$ x \equiv_L y \iff \forall z \in \Sigma^*: xz \in L \Leftrightarrow yz \in L $$ Es decir, dos palabras son equivalentes, si sin embargo añadimos algún $z$ a ambos, o bien tenemos que palabras en $L$ o dos palabras menos $L$ .

Normalmente se mira $\equiv_L$ para ver si una lengua es o no regular. Para ver que una lengua no es regular, hay que dar infinitas palabras $x_i \in \Sigma^*$ con $$ x_i \not\equiv_L x_j, \qquad i \ne j $$ Es decir, por qué te dieron esos $z$ s, serán útiles para ver que sus clases listadas son realmente diferentes. Por ejemplo:

$\epsilon \not\equiv_L a$ como con $z = b$ (mire su $K_A$ lista), tenemos $\epsilon z = b \not\in L$ pero $az = ab \in L$ .

Obsérvese además que basta con una lista infinita, es decir, si se puede demostrar $a^i\not\equiv_L a^j$ para $i \ne j$ has terminado de demostrar que $L$ no es regular. Si quieres encontrar todas las clases de equivalencia, falta al menos una.