5
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ To get braces add a backslash like $\{$ for $\{$ $\endgroup$
    – quid
    May 20, 2016 at 13:48

2 Answers 2

6
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ May 20, 2016 at 14:14
  • $\begingroup$ Huge thanks! Helped me a lot! $\endgroup$
    – A-H
    May 20, 2016 at 14:19
  • $\begingroup$ 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 $\endgroup$
    – A-H
    May 20, 2016 at 14:21
1
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .