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

Question

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.

Answer 1

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.