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

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?

• To get braces add a backslash like $\{$ for $\{$ – quid May 20 '16 at 13:48

## 2 Answers

Take the string $a^qb^q$, where $q$ is any prime greater than the constant given by the pumping lemma.

• But so the gcd(m,n) = 1 and the string isn't in L. Am I lose something? Thank you – A-H May 20 '16 at 14:07
• I think that gcd(q,q)=q. Indeed, q divides both numbers and is obviously the greatest number dividing q and q. – Orlando Marigliano May 20 '16 at 14:18
• Got it. Thanks a lot – A-H May 20 '16 at 14:23

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$.

• Oops. The string $a^qb^q$ would also work with almost the exact same reason. Got caught up thinking about different numbers for some reason. C'est la vie. – Meta-мета-μετα-meta-мета-μετα May 20 '16 at 14:14
• Huge thanks! Helped me a lot! – A-H May 20 '16 at 14:19
• Why $a^qb^q$ would also work? I cant choose this word cause it's not in the language no? (gcd(m,n)=1) edition: Got my mistake. Sorry – A-H May 20 '16 at 14:21