So I have a language: $$ L = \{a^{n^2} \mid n > 0\} $$ I need to prove that this language isn't context-free using the pumping lemma. I have a vague thought process as to how to do the proof but I'm sort of doubting its validity.

So I take a pumping length $p$ such that a word $a^{p^2}$ can be split into 5 parts $uvxyz$. I need to assume that $L$ is context-free and run through some cases and check if the word violates the pumping lemma or if it doesn't violate the pumping lemma but isn't in the language definition.

I know the concept of proving languages aren't context free and the pumping lemma but I'm very stuck applying it to this particular language.

What do I do?

  • $\begingroup$ What happens when you "pump" that string of $n^2$ times $a$? How long can you make it by pumping? Can you pump it so that its length is no longer a square? $\endgroup$ – chi May 13 '16 at 13:12
  • 2
    $\begingroup$ Since all of $u,v,x,y,z$ consist entirely of $a$s, this is simple. Hint: show that $uv^ixy^iz$ has length greater than $p^2$ and less than $(p+1)^2$ for some suitable value of $i$. $\endgroup$ – Rick Decker May 13 '16 at 13:17
  • 1
    $\begingroup$ Possible duplicate of How to prove that a language is not context-free? $\endgroup$ – DylanSp May 13 '16 at 14:31
  • 2
    $\begingroup$ @DylanSp I don't think this is a duplicate. The asker is aware of the general techniques available but is asking about a specific attempt to prove that aspecific language isn't context-free. $\endgroup$ – David Richerby May 13 '16 at 18:43

[Since (a) this is an instance of a standard problem and (b) I wasn't able to find it in the archives, I'll expand my comment into a hinted solution.]

As usual in problems like this, we assume that the language $L$ is context free, so the Pumping Lemma applies, meaning that there is an integer $p>0$ such that we can write the string $a^{p^2}$ as the concatenation of strings $uvxyz$ with $|vy|>0$ and $|vxy|=t\le p$. Hence, we'll have $$ 0 < |vy|=t\le p $$ This means that when we pump $uvxyz$ to $uv^ixy^iz$ we'll have $$ p^2<|uv^ixy^iz|=p^2+(i-1)t\le p^2+(i-1)p $$ Choosing $i=2$ gives us $$ p^2<|uv^2xy^2z|\le p^2+p $$ Now, in length order, the next string in $L$ after $a^{p^2}$ will be $a^{(p+1)^2}$. Here's the hint: use this fact to show that $uv^ixy^iz$ can't possibly be in $L$, contradicting the Pumping Lemma consequence that all the pumped strings are in $L$, so consequently $L$ cannot be a CFL.

This idiom, BTW, can be used to show that other languages over a one-symbol alphabet aren't context-free, like the $a^{n^5}$ language or the $a^p$ language, where $p$ ranges over the primes. There are more general results, as well, like the one that says that any CFL over a one-symbol language is regular. That, along with another theorem that says, roughly, that a regular language over a one-symbol language can't be too "sparse", gives a higher-level proof of your question.


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.