1
$\begingroup$

I'm not very comfortable with pumping lemma for context-free grammar. I understand the sufficient conditions that must hold but proving it gets me everytime. For example, I need to prove whether $L = \{0^{n^3} \mid n\in\mathbb{N}\}$ is context-free or not.

Based on my intuition, it won't be. There is no pattern of $0$'s that can be recreated by a pushdown automata but alas I need to prove this. I know you start off assuming it is by being able to create a substring $uvxyz$ where $v$ and $y$ are raised to the $i$th power where $i \ge 0$. I'm having trouble from there, any help in this and the understanding would be greatly appreciated.

$\endgroup$
1
  • $\begingroup$ You can use Parikh's theorem to prove that this language is not context-free (but it isn't the most direct way unless you already know Parikh's theorem). $\endgroup$ – Gilles 'SO- stop being evil' Oct 15 '13 at 23:43
1
$\begingroup$

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| > 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| > 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.

$\endgroup$
2
  • $\begingroup$ Hey, I was wondering where the $-t$ came from in $0^{m3−t+it}$. $\endgroup$ – Andrew Reynolds Mar 26 '14 at 5:17
  • $\begingroup$ Hint: When $i = 1$, we should be getting $0^{m^3}$. $\endgroup$ – Yuval Filmus Mar 26 '14 at 14:03

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.