[Math] Pumping Lemma for $L= \{a^{m}b^{n}| m,n > 0 , \gcd(m,n) > 1 \}$

automatapumping-lemmaregular-language

Let language $L= \{a^mb^n \mid m,n > 0 , \gcd(m,n) > 1\} $ above the alphabet $\Sigma = \{a,b\} $ .

I need to prove by the pumping lemma that $L$ is not a regular language but I am having trouble finding a string I can pump resulting in the string not being in the language.

EDITION:

On the next section, I need to proove that $L= \{a^mb^n \mid m,n > 0 , \gcd(m,n) = 1\} $ is not a regular language. I cant use the pumping lemma. I need to relate that L (of the previous section) is not regular, and relate the closure rules. But how do I relate to the closure when I have a NOT regular language as a given?

Any suggestions?

Best Answer

If $p$ is a proposed pumping length, let $q > p$ be prime, and consider the string $w = a^qb^{(q^2)} \in L$. (Clearly $|w| = q+q^2 \geq p$.)

Let $w = xyz$ be a decomposition such that

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

In follows that $y = a^k$ for some $1 \leq k \leq p < q$, and so "pumping" it zero times results in the string $$ xy^0z = xz = a^{q-k}b^{(q^2)}$$ where $1 < q-k < q$. As the only factors of $q^2$ are $1,q,q^2$ (remember that $q$ is prime) it follows that $\operatorname{gcd} (q-k,q^2) = 1$, so $xy^0z$ is not in $L$.

Related Question