Ejemplos de uso del teorema de Myhill y Nerode

Investigamos de nuevo el lenguaje

$$L=\{a^nb^n\;\vert\;n\in\bbbn, n>0\}$$

anotamos unas clases de equivalencia de $L$:

$$\begin{eqnarray*}[ab]&=& L \\ {}[a^2b]&=&\{a^2b,a^3b^2,a^4b^3,\dots\}\\ &\dots& \\ {}[a^kb]&=&\{a^{k+i-1}b^i\;\vert\;i\ge 1\} \end{eqnarray*}$$

verificamos que son clases de equivalencia, porque si $a^{k+j-1}b^j\in[a^kb]$ y $a^{k+l-1}b^l\in[a^kb]$ entonces o bien $a^{k+j-1}b^jz,a^{k+l-1}b^lz\in L$ (si $z=b^{k-1}$) o bien $a^{k+j-1}b^jz,a^{k+l-1}b^lz\notin L$ (si $z\not=b^{k-1}$).

Por eso el número de clases de $R_L$ es infinito, es decir, $\mathrm{Indice}(R_L)=\infty$.

Observa que no hemos clasificado todas las palabras de $\mbox{$\Sigma^*$}$, sino solamente algunas palabras posibles:

$$\mbox{$\Sigma^*$}=L\cup \underbrace{[a^2b]\cup\dots\cup[a^kb... ... infinito}} \underbrace{\cup\dots}{\mbox{las dem\'as clases}}$$

es decir, para comprobar que un lenguaje no es regular basta con encontrar un número infinito de clases de equivalencia (respecto a la relación $R_L$).

Investigamos el lenguaje

$$L=\{w\;\vert\;w\in\{0,1\}^* \mbox{ y $w$ termina con 00}\}$$

Pensamos en las posibles clases de equivalencia. Obviamente hay tres, o bien una palabra no termina en 0, o bien termina en un 0, o bien termina por lo menos en dos 0, es decir:

$$\begin{eqnarray*}[\epsilon]&=&\{w\;\vert\;w \mbox{ no termina en 0}\} \\ {}[0]&... ... un solo 0}\} \\ {}[00]&=&\{w\;\vert\;w \mbox{ termina en 00}\} \end{eqnarray*}$$

Con $\mbox{$\Sigma^*$}=[\epsilon]\cup[0]\cup[00]$ seguimos la construcción de arriba y obtenemos la tabla de transiciones para el autómata:

	$0$	$1$
$\Longrightarrow [\epsilon]$	$[0]$	$[\epsilon]$
$[0]$	$[00]$	$[\epsilon]$
$\star [00]$	$[00]$	$[\epsilon]$

o como diagrama: