# Proof that $\{0^i1^{i^2}:i\in\mathbb{N}\}$ is not context free

I am to prove that $$L :=\{0^i1^{i^2}:i\in\mathbb{N}\}$$ is not context-free. I presume that I can do this with the Pumping Lemma and the word $$0^p1^{p^2}$$, where we assume for a contradiction that $$L$$ has a Pumping Length of $$p$$, and here's my attempt:

Let $$0^p1^{p^2}=uxyzv$$ such that $$xz$$ is non-empty, $$xyz$$ is of length $$\le p$$ and $$ux^iyz^iv\in L$$.

• Case 1: if $$xyz$$ is entirely within $$0^p$$ then $$ux^2yz^2v = 0^p0^k1^{p^2}$$ for some $$k>0$$ and hence $$ux^2yz^2v \notin L$$.
• Case 2: if $$xyz$$ is entirely within $$1^{p^2}$$ then we get the same contradiction (with $$0^p1^{p^2}1^k$$).
• Case 3: suppose that $$x = 0^i$$, $$z = 1^j$$. Then $$ux^0yz^0v=0^{p-i}1^{p^2-j}$$.

Then I want to show that $$(p-i)^2 \ne p^2-j$$, but I'm not sure how to do this.

• Yes I did - fixed. – Adam Jul 16 at 8:58

The simplest way to show that your language is not context-free is by reduction to unary alphabet. Suppose that your language were context-free. Then the language obtained by applying a homomorphism which deletes all $$0$$'s would also be context-free. This language is the unary language $$L' = \{ 1^{i^2} : i \notin \mathbb{N} \}$$. It is known that a unary language is context-free iff it is regular. You can prove that $$L'$$ isn't regular in any number of ways (for example, it is finite but its limiting density is zero).
If you are hell-bent on using the pumping lemma, then the following argument works. As you mention, the only interesting case is Case 3, in which $$x = 0^i$$ and $$z = 1^j$$. According to the pumping lemma, for every $$t$$ the word $$ux^{1+t}yz^{1+t}v = 0^{p+ti} 1^{p^2+tj}$$ must belong to $$L$$, that is, $$p^2+tj = (p+ti)^2$$. But $$(p+ti)^2 = \Theta(t^2)$$ whereas $$p^2+tj = \Theta(t)$$, so for large $$t$$ the two cannot be equal.