How would you prove that the following language is not context-free?

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

I suspect the solution uses the pumping lemma, but I'm not sure how to apply it.

  • $\begingroup$ if you pump up you have $a^{n+k}b^{m+k}$ so how can you proove that gcd(n+k,m+k)\neq 0$ ? $\endgroup$ – Eren Bellisoy Apr 5 '12 at 21:36
  • $\begingroup$ Nope. It is not a regular language. you cannot pump y all alone. $\endgroup$ – Eren Bellisoy Apr 6 '12 at 6:04
  • $\begingroup$ Please check the methods shown in our reference question and focus your question. If pumping lemma is going to work, you are likely to need some number theory (for finding the correct pumping factor $i$). $\endgroup$ – Raphael Jul 18 '12 at 0:31

Let $p$ be the pumping length guaranteed by the pumping lemma (for context free languages). Then we choose $m \neq n$ such that $m,n \geq p$ and are both prime. Then clearly $s = a^{n}b^{m} \in L$.

By the pumping lemma we can divide $s$ such that $s=uvxyz$ and

  1. $|vxy| \leq p$
  2. $|vy| \geq 0$
  3. $s' = uv^{i}xy^{i}z \in L$ for all $i \in \mathbb{N}$

For this language we get three similar cases, and one trivial case. The trivial case is where either $v$ or $y$ contains both $a$'s and $b$'s, in which case $s'$ doesn't have the correct ordering, and thus $s'\notin L$.

The nontrivial cases:

  1. $v$ and $y$ are both strings of $a$'s, then when we pump $s$ we get $s' = a^{n+ik}b^{n}$ where $k\geq 1$. Then $s' \in L$ if $gcd(n+ik,m)=1$, however the modular equation $n+ik\equiv 0 (m)$ has the solution $i \equiv nk^{-1} (m)$, and as $m$ is prime we are guaranteed that $k^{-1}$ exists. Therefore any element of the residue class $i \equiv nk^{-1} (m)$ would give us $gcd(n+ik,m) > 1$. Ergo $s' \notin L$.

    Short version: we can pump the string so that $n+ik$ is a multiple of $m$ for any $k$ with $1 \leq k \leq p < m,n$ (which is what we set up at the start).
  2. $v$ and $y$ are both strings of $b$'s, but this case is just the symmetric case to case 1, so we derive a contradiction in this case too.
  3. $v = a^{k}$ and $y = b^{h}$ for some $k$ and $h$ with $1 \leq k+h \leq p$. Then when we pump we get $s' = a^{n+ik}b^{m+ih}$. Now $s' \in L$ if $n+ik \equiv m+ih (m)$ has no solution, but as I'm sure you can see from here, rearranging just gives $n+i(k+h)\equiv 0(m)$, and as before this has solution $i \equiv n(k+h)^{-1}(m)$. So again we derive a contradiction.

Thus there is at least one string in $L$ that cannot be divided as per the pumping lemma and still have all pumping results remain in $L$. Therefore $L$ is not context free. $Q.E.D$

Some additional notes: of course there is an infinite number of strings which can't be pumped, and it's not actually necessary for $m$ and $n$ to be prime, it just simplifies that argument, as we don't have to fiddle around with a prime decomposition - though if you did want to, you just pick one of the prime factors and do the same (or even all of them if you want).

  • $\begingroup$ Note that your $i$ is the Pumping-$i$ plus one: you can never "unpump" times (which you don't need). If you wanted to allow that, you'd have to have $a^{n-k +ik}$ and similar for the second part. $\endgroup$ – Raphael Jul 18 '12 at 10:17

Trick: A language is not Context free language if it has same Comaprision more then one times For Instance :L = {a^nb^c^n|n>0} as you know this is not context free why:? as you can see number of b shuld be same as the number of a "This is first Comarision" and after that again number of c shuld be same of the number of b or number of previous a.Here 2 stack is needed to remember for equal number of occurance of a and b.so this is not "pda" because you know pda has only one stack...

Another Beautifull Example: L={a^nb^na^mb^m|m,n >0} Tell me weather this language is CFL or not. 

Again Here Look for number of Comparision between same Entity: Here Number of b shuld be same as number of a...In case of a^nb^n...Here only one comarision between "n" now move to the a^mb^m Again here number of b depend up on number of a, where number of doesn't depend on any one so between a and b for power m only one comparision is going on that's why it is L={a^nb^na^mb^m|m,n >0} is CFL

Ex: L = {a^nb^ma^nb^m | m>n>0} Tell me weather It's CFL or not By seeing number of comaprision Answer: Yes This is CFL

Now Lets move to your Questions:

L= {a^n,b^m | gcd(n,m)=1}

Here we are restricted to choose value of n and m...so that it's gcd always come 1.... Find Comarision Here:

 What Will be the value of m,n ???
 It's depend upon condition that whenever you will choose value of m, or n it shuld be either > and equal to m in case of value selection for m or same for value selection for m (This is first comarision between m and n or reverse for selecting value)  Now think 

Another comaprision : GCD of m, n shuld be 1 (This is another comarision for m, n) so here two comarision is present show it is not CFL.

 And Acrding to pumping Lemma Theorem:
    1)Select any string belongs to L
    2)devide it in xYz part make sure that Y shuld not have o length.
    3)Take any value of "i" acrding  to your wish.
    4)make x(Y)^iz and check weather it's belong to L if not then it will prove that it is not regular. i>and equal to 1.

Think: Can you construct a PDA For this, Condition you have one one Stack...Defenately You will come to conclusion ...If you still didn't get my point I will write more for you....

  • $\begingroup$ I got your point however since it is not a regular language, I cannot use xYz notation.I need to use uVxYz notation. So whenever I pump up i will have 3 possibilities; a^n + k ,b^m ;a^n + k, b^m +k; a^n, b^m +k . So i need to show on all of those possibilities it wont be belong to L anymore. So how? $\endgroup$ – Eren Bellisoy May 14 '12 at 19:39
  • 2
    $\begingroup$ "Trick: A language is not Context free language if it has same Comaprision more then one times" -- oh dear. That's nowhere near a formal or precise statement. $\endgroup$ – Raphael Jul 17 '12 at 22:58

Your Answer

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