Bombeo Lema para $L= \{a^{m}b^{n}| m,n > 0 , \gcd(m,n) > 1 \}$

Question

Vamos idioma $L= \{a^mb^n \mid m,n > 0 , \gcd(m,n) > 1\} $ por encima del alfabeto $\Sigma = \{a,b\} $ .

Tengo que demostrar por el lema de bombeo que $L$ no es un lenguaje regular, pero estoy teniendo problemas para encontrar una cadena que puedo bomba resultante en la cadena no está en el lenguaje.

EDICIÓN:

En la sección siguiente, tengo que probar ese $L= \{a^mb^n \mid m,n > 0 , \gcd(m,n) = 1\} $ no es un lenguaje regular. No puedo utilizar el lema de bombeo. Necesito al ver que L (de la sección anterior) no es regular, y lo relacionamos con el cierre de las reglas. Pero, ¿cómo se relacionan con el cierre cuando tengo un NO lenguaje regular como un dado?

Alguna sugerencia?

Answer 1

Si $p$ es una propuesta de bombeo de longitud, deje $q > p$ primo, y considerar la cadena de $w = a^qb^{(q^2)} \in L$. (Claramente $|w| = q+q^2 \geq p$.)

Deje $w = xyz$ ser una descomposición tal que

• $y \neq \varepsilon$, y
• $|xy| \leq p$.

En la siguiente que $y = a^k$ algunos $1 \leq k \leq p < q$, y así el "bombeo" de cero veces los resultados en la cadena de $$ xy^0z = xz = a^{q-k}b^{(q^2)}$$ where $1 < q-k < q$. As the only factors of $q^2$ are $1,p,q^2$ (remember that $p$ is prime) it follows that $\operatorname{mcd} (q-k,q^2) = 1$, so $xy^0z$ is not in $L$.

Answer 2

Tome la cadena de $a^qb^q$ donde $q$ es cualquier prime mayor que la constante dada por el lema de bombeo.