1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes I did - fixed. $\endgroup$ – Adam Jul 16 at 8:58
1
$\begingroup$

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.

$\endgroup$

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.