4
$\begingroup$

There is a problem which I cannot solve. If you give a tip I will be very glad.

Prove that following language is not context free:

$L= \{ a^nb^m | \gcd(n,m) = 1 \}$.

It can be proven using the pumping lemma, but how?

If I start with some prime numbers $m$ and $n$ where $m>n>2$ and pump it up from $uVxYz$, there are three possible outcomes: $a^{n + k} b^m$, $a^{n +k}b^{m +k}$, $a^n b^{m +k}$. Since I do not know whether $k$ is even or odd I cannot say something. It is certain that $a^n$ and $b^m$ will be odd. However after adding $k$ to some of them, how can I say something about whether their gcd is 1 or not?

Improve this question
$\endgroup$
1
  • 6
    $\begingroup$ Please read this reference question and edit the question to explain where specifically your attempts fail. As it is, I consider this question to be a duplicate. $\endgroup$
    – Raphael ♦
    May 14, 2012 at 19:52

1 Answer 1

Reset to default
2
$\begingroup$

Hint...

There may be a direct application of the pumping lemma, but I suggest you take a look at closure properties. Consider the non-CFL in the first answer to the reference post, $P=\{a^p:p \text{ prime}\}$, which is clearly a cousin of $L$. Can you find a (fairly simple) operation on $L$ that preserves CFLs and more or less yields $P$? If so, you are done, except perhaps to tidy up with some other operations to deal with special cases for $P$.

In general, when languages are relatively "dense", that is, have a high proportion of members to non-members for all given lengths, it's harder to apply pumping arguments, because it's more work to pump to get outside the "dense" set; in fact, sometimes it's impossible. $P$ is a nice "sparse" set, so pumping works well, as shown in the reference post. $L$ is quite a bit "denser", so transforming it to a "sparser" form is a good tactic to try.

The classical example of this principle (for non-regular languages) is the very dense set $\{a^ib^j:i \neq j\}$ and the corresponding sparse set is $\{a^ib^i\}$. The operation in this case is complement, again with a "cleanup" operation needed as well. As part of the above hint, the operation there is not complement, which doesn't work for CFLs anyway.

Improve this answer
$\endgroup$
7
  • $\begingroup$ So if i pump up P i will have a^p +k. if i pump up p times, i will have a^(k+1)*p . So since it is not a prime number i prooved that it not context free. However prooving that a number is not prime, and prooving that two numbers is not prime relative to each other very different things. How can i relate P with L ? $\endgroup$
    – user1494
    May 17, 2012 at 23:07
  • $\begingroup$ CFLs are closed under a number of operations -- you can look some of them up here in Wikipedia and other places. So if you assume $L$ is a CFL and find a sequence of those operations to transform $L$ into $P$, that would show that $P$ is also a CFL, which is a contradiction with what you just showed. So you could conclude that $L$ is not a CFL. A hint on which operations might work: look at what alphabets $L$ and $P$ use. You might also need some simple algebra regarding divisibility and factoring. $\endgroup$
    – David Lewis
    May 18, 2012 at 2:51
  • $\begingroup$ So here it is: $P= \{ a^n | n \ is\ prime \}$. $P2 = \{b^m | m\ is\ prime\}$ and then let $L1 = \{ a^n, b^m | n,m\ is\ prime\} $ let L2 be $L2 = \{ a^n,b^m | gcd(n,m)= 1 , n\ and\ m\ is\ not\ prime\ numbers\} $. From now on we can see L1 = P.P2 and L = L1 U L2. So in order L to be context free, L1 should be context free, in order L1 to be context free P should be context free. Since we proved P is not context free, so L1 is not context free, therefore L is not context free. $\endgroup$
    – user1494
    May 19, 2012 at 5:12
  • $\begingroup$ I don't think that works. What are the operations that actually apply to $L$ to get you to $P$? You have it the other way around, and some of the operations you'll need for this approach do not preserve CFLs. It's much simpler. You need to reduce the alphabet of $L$ to the alphabet of $P$. A simple operation that preserves CFLs and might do that is homomorphism. If you're not familiar with homomorphism, there's a link in the Wikipedia article. $\endgroup$
    – David Lewis
    May 19, 2012 at 12:15
  • $\begingroup$ ı think that works. I used union and concetanation. both of them are closed. Where do you think the mistake is? $\endgroup$
    – user1494
    May 20, 2012 at 1:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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