Prove that {0^{n^3} | n≥0} is not context free
Gilles suggests a sophisticated method for solving this exercise, which is also the "proper" method; we will say more about it below. But let's start with applying the pumping lemma. The pumping lemma states that if $L$ is context-free then there exists some integer $n$ such that all words $w \in L$ of length at least $n$ can be written in the form $w = uvxyz$ with $|vxy| \leq n$ and $|vy| &gt; 0$ (i.e. not both $v,y$ are empty), such that $uv^ixy^iz \in L$ for all $i \geq 0$.

Let's see what this means in your case. Suppose $L$ were context-free, and let $n$ be the integer given by the pumping lemma. Take some $m$ satisfying $m^3 \geq n$. Since $0^{m^3} \in L$ and the word has length at least $n$, we can write $0^{m^3} = uvxyz$ such that $|vy| &gt; 0$ and $|vxy| \leq n$, and furthermore $uv^ixy^iz \in L$ for all $i \geq 0$. So $vy = 0^t$ for some $1 \leq t \leq n$, and for all $i \geq 0$, $0^{m^3-t+it} \in L$, that is, for all $i \geq 0$, $m^3 + (i-1) t$ is a cube. Your mission is to somehow reach a contradiction from this data.



Now for Gilles' proof. We can consider the language $L$ over the unary alphabet $\Sigma = \{0\}$. Parikh's theorem states that $L$ is context-free iff it is regular. The proof is not difficult: if $L$ is regular then it is context-free, and in the other direction you take a grammar for $L$ and massage it into an equivalent right-regular grammar; the idea is that $xy = yx$ if $x,y \in 0^*$.

The next step is to find a criterion for when a language $L_A = \{ 0^n : n \in A \}$ is regular. By considering a DFA for $L_A$, it is not hard to show that $L_A$ is regular iff $A$ is eventually periodic, that is, for some $a \geq 0$ and $b \geq 1$ it is the case that $x \in A$ iff $x + b \in A$ for $x \geq a$. This is not the case for the set of cubes, since the gap between adjacent cubes tends to infinity. We conclude that $L$ isn't regular nor context-free.