How can I prove that $\{0^n 1^{n^2} \mid n \in \mathbb{N}\}$ is not a context free language?

I tried to prove it using the pumping lemma, but I don't know how to deal with the case when $vxy$ contains both $0$ and $1$.

  • $\begingroup$ Welcome to Computer Science! Your question is a very basic one. Since you did not include much of an attempt to solve it on your own, we have little to work with. Let me direct you towards our reference questions which cover your problem in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Your question may then be reopened. Good luck! $\endgroup$ – Raphael Apr 29 '13 at 10:39

If $v x y$ is just 0s or 1s, pumping does unbalance the 0s and 1s.

If $v$ is $0^a$ and $y = 1^b$, pumping once gives $0^{N + a} 1^{N^2 + b}$, now prove that that can't possibly work out as $a + b \le N$ (in particular, $N^2 + b$ can't be a perfect square).


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.