1
$\begingroup$

This question already has an answer here:

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^{2^n}∣n \geq 0\}$ is not context-free.

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≥0$. I'm having trouble from there, any help in this and the understanding would be greatly appreciated.

$\endgroup$

marked as duplicate by David Richerby, Raphael Apr 13 '15 at 21:59

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ See meta.cs.stackexchange.com/questions/599 and more specifically cs.stackexchange.com/questions/265/… $\endgroup$ – babou Apr 13 '15 at 15:53
  • $\begingroup$ Maybe you should go back to the statement of a lemma, it says that, if the language is CF, then there is a number $p$ such that, if a sentence is longer than $p$ then ...it can be decomposed so that ... and that gives you a set of other strings that must be in the language ... but for some reason (that may vary) sme of these strings cannot be ... so the language is not CF. $\endgroup$ – babou Apr 13 '15 at 16:02
0
$\begingroup$

A unary language (a language over a unary alphabet) is context-free if and only if it is regular. The easiest way to see this is to convert a context-free grammar to a regular grammar using the fact that $xy = yx$ over a unary alphabet.

There are many ways of showing that $L$ is not regular, and so not context-free. One way is using the Myhill–Nerode criterion. Since $0^{2^n} 0^{2^n} \in L$ while $0^{2^m} 0^{2^n} \notin L$ for $m \neq n$, we see that the words $\{ 0^{2^n} : n \geq 0 \}$ are pairwise inequivalent, and so $L$ is not regular.

A proof using the pumping lemma is also not too difficult. Given a pumping length $n$, choose $m$ so that $2^{m-1} > n$, and consider the word $0^{2^m} \in L$. According to the pumping lemma you can write $0^{2^m} = xyz$ with $|xy| \leq n < 2^{m-1}$ and $|y| \geq 1$ so that $xz \in L$. But $xz = 0^{2^m-|y|}$ cannot be in $L$ since $2^{m-1} < 2^m-|y| < 2^m$. This contradiction shows that $L$ is not regular.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.