2
$\begingroup$

Show that L = $\{0^{2^n}| n\geq 0\}$ is not a context free language.

Let string $s = 0^{2^p}$. Then we know we can write $s$ as $s = uvxyz$. I know that |vy| > 0 and $|vxy| \leq p$.

So how do I show that $uv^2xy^2z$ is not in $L$.

$\endgroup$
  • 2
    $\begingroup$ It's not. Have you considered pumping lemma? $\endgroup$ – Karolis Juodelė Sep 22 '13 at 19:24
4
$\begingroup$

$\{ 0^{2^n} \mid n \ge 0 \}$ is not context-free.

To show this, you can use any of the usual techniques to show that a language is not context-free, such as the pumping lemma for context-free languages.

The pumping lemma states that if $L$ is context-free, then there exists a pumping length $p$ such that for all $n \ge p$, there exist $u,v,x,y,z$ such that $0^{2^n} = uvxyz$ and $|vy| \ge 1$ and for all $k \ge 0$, $uv^kxy^kz \in L$. Take $n = p$: for all $k \ge 0$, $|uv^kxy^kz| = |uxz| + k |vy|$ must be a power of $2$. This is not possible for large $k$ since it would imply that the distance between consecutive powers of $2$ is never more than $|vy|.

You can also use Parikh's theorem, which states that the set of possible numbers of occurrences of a letter in a context-free language is semi-linear (i.e. it's of the form $\{a p + b \mid a \in \mathbb{N}, b \in B\} \cup C$ for some integer $p$ and some finite sets $B$ and $C$). For a language with a singleton alphabet, this means that the set of lengths of words in the language is semi-linear, which $\{2^n \mid n\in\mathbb{N}\}$ isn't.

$\endgroup$
  • $\begingroup$ I choose the string s = 0^2^p. But I'm not sure how to argue by cases to show you can't pump up the string. $\endgroup$ – user678392 Sep 22 '13 at 21:29
  • $\begingroup$ @user678392 For this language you don't need any case analysis, you just write the decomposition and show that you can construct some word that isn't in the language. Where are you stuck? $\endgroup$ – Gilles Sep 22 '13 at 21:35
  • $\begingroup$ You can't simply show that some word is not in the language, you have to show that for some string every partition of that word is not in the language. And thus you need case analysis to cover all the different partitions. This is what I'm stuck on. $\endgroup$ – user678392 Sep 22 '13 at 21:37
  • $\begingroup$ @user678392 No, that's not quite it. The way a pumping lemma proof works is to show that if the language is regular/context-free then there is a word in the language which can be decomposed in such a way as to build new words that are in the language according to the pumping lemma, but are actually not in the language according to its definition. Often you need to make a case analysis in order to match the pumping lemma decomposition with the decomposition in the language definition, but here the language definition is so simple that there is only one case. $\endgroup$ – Gilles Sep 22 '13 at 21:40
  • $\begingroup$ I don't see how there is only one case. That is what I don't see. $\endgroup$ – user678392 Sep 22 '13 at 21:42

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.