4
$\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$
  • $\begingroup$ To get braces add a backslash like $\{$ for $\{$ $\endgroup$ – quid May 20 '16 at 13:48
0
$\begingroup$

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

$\endgroup$
  • $\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 '16 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$ – Orlando Marigliano May 20 '16 at 14:18
  • $\begingroup$ Got it. Thanks a lot $\endgroup$ – A-H May 20 '16 at 14:23
5
$\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$
  • $\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$ – Meta-мета-μετα-meta-мета-μετα May 20 '16 at 14:14
  • $\begingroup$ Huge thanks! Helped me a lot! $\endgroup$ – A-H May 20 '16 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 '16 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.