Demostrar la irregularidad del lenguaje mediante el teorema de Nerode

Question

Dejemos que $L=\{b^ma^n|m \space and \space n \space are \space coprime \}$ utilizando el teorema de Nerode demostrar que $L$ es irregular.

Del teorema de Nerode sé que $L$ es regular si y sólo si el número de clases de equivalencia de $R_L$ (la relación definida en el teorema de Nerode) es finita, por lo que necesito demostrar que hay un número infinito de clases de equivalencia.

Lo primero que me vino a la mente de $L$ La definición de Dirichlet se basa en el teorema de Dirichlet, por eso lo he intentado:

Dejemos que $w_{m, i}=b^ma^i$ , ( $m,i$ son coprimas), y demuestro que para $j\ne i$ , ( $m, j$ coprimas), $$w_{m, i} \not R_L w_{m, j}$$ Dejemos que $z=a^{m+ni}$ , ( $n$ un número entero prometido por el teorema de Dirichlet tal que $m+ni$ et $m$ son coprimas), por lo que $$w_{m, i}z = b^ma^{m+ni+i}= b^ma^{m+(n+1)i}\in L$$ y $$w_{m, j}z = b^ma^{m+ni+j}\not\in L$$ Pero esto no es necesariamente cierto ya que $m$ et $m+(n+1)i$ pueden no ser coprimas y $m$ et $m+ni+j$ puede ser

Sé por ejercicios anteriores que necesito encontrar $w_i$ y mostrar que para una palabra $z$ $$w_iz\in L \space and \space w_jz\not\in L \space\space (i\ne j)$$ y por lo tanto hay un número infinito de clases de equivalencia, pero me parece difícil con todo el primo/coprimo

Answer 1

No es necesario un argumento avanzado de teoría de números para demostrar este resultado. Afirmo que si $p$ et $q$ son primos distintos, entonces $(b^p)^{-1}L \not= (b^q)^{-1}L$ . Supongamos por contradicción que $(b^p)^{-1}L = (b^q)^{-1}L$ . Desde $p$ et $q$ son coprimos, se tiene $b^pa^q \in L$ . De ello se desprende que $a^q \in(b^p)^{-1}L$ De ahí que $a^q \in(b^q)^{-1}L$ Es decir, $b^qa^q \in L$ una contradicción.

Se deduce que los cocientes $(b^p)^{-1}L$ , para $p$ primo, son todos distintos, y por lo tanto $L$ no es regular.