2
$\begingroup$

I'm having difficulty trying to use the pumping lemma in order to show that $L= \{0^i \mid \ i \text{ is a power of 2 }\} $ is not context free.

I"m starting by stating that $ s = 0^p$ and then $ s = uvxyz $ and that in order for a language to be context free it must follow the 3 conditions: $|vy| > 0$ , $|vxy|\le p$ and for some $m \ge 0, \, uv^mxy^mz \in L$.

So I guess I"m struggling on how pumping something $uv^mxy^mz$ will not be in $L$. Would I try and use something along the lines of pumping down $uv^0xy^0z$ for this to not be in $L$. Any help greatly appreciated!

$\endgroup$
5
  • $\begingroup$ Asumme $L$ is CFL. Let $k$ be the constant of the pumping lemma. let $z=0^{2^k} \in L$.. from the lemma we get that $z=uvwxy$. Consider $uv^2wx^2$. by the lemma, it's in $L$. What can you say about the length of this word? Try prooving that the length isn't a power or 2 $\endgroup$
    – Roi Divon
    Oct 26 '14 at 17:03
  • $\begingroup$ Okay that makes sense, so with $uv^2wx^2y$ the length of this would be an odd length if u, v, and y are all raised to 1, so $u^1v^2x^1y^2z^1$ is an odd length. $\endgroup$ Oct 26 '14 at 17:13
  • $\begingroup$ It's not true. you don't know what $u,v,w,x$ and $y$ are. Try showing that $2^k < |uv^2wx^2y| < 2^{k+1}$ $\endgroup$
    – Roi Divon
    Oct 26 '14 at 17:18
  • $\begingroup$ Hmm, you're right, we wouldn't know what u,v,w,x and y are. Now I might be more lost, I'll keep reviewing. Thank you. $\endgroup$ Oct 26 '14 at 18:12
  • 1
    $\begingroup$ Our reference question may provide some clues. $\endgroup$
    – Raphael
    Oct 27 '14 at 13:45
3
$\begingroup$

If you're still confused, here's the proof. Let $p$ be the integer of the Pumping Lemma and consider the string $0^{2^p}$. If $L$ was a CFL, then (since $2^p\ge p$) the PL would apply to $0^{2^p}$ we'd have $0^{2^p}=uvxyz$ with

  1. $|vxy|\le p$
  2. $|vy| > 0$

So if we let $v=0^k, y = 0^j$, we have from (1), $k + j =|vy| \le |vxy| \le p$ and from (2), $k + j=|vy|>0$. In other words,

$0<k+j\le p$

Now pump up: The PL assures us that $uv^2xy^2z\in L$, and observe $$ |uv^2xy^2z| = 2^p+(k+j)\le 2^p+p< 2^p+2^p=2^{p+1} $$ as long as $p>0$, so the pumped string $uv^2xy^2z$ has length strictly between $2^p$ and $2^{p+1}$. No such string can be in $L$, so we have a contradiction to the PL implication that $uv^2xy^2z\in L$ and so our initial assumption, that $L$ was a CFL, must be false.

You could shorten this proof if you knew that (1) any context-free language over a 1-symbol alphabet must be regular and (2) the language $L=\{0^{2^n}\mid n\ge 0\}$ is not regular.

$\endgroup$
1
  • $\begingroup$ Thank you Rick, that clears up the confusion I had about letting $v = 0^k, \, y=0^j$ very helpful! $\endgroup$ Oct 26 '14 at 22:50
2
$\begingroup$

Instead of getting bogged down in the details of the pumping lemma, you can use the Myhill–Nerode criterion. For any $a<b$, the words $0^{2^a},0^{2^b}$ are inequivalent modulo $L$ since $0^{2^a} 0^{2^a} \in L$ while $0^{2^b} 0^{2^a} \notin L$. This gives an infinite number of pairwise inequivalent words, showing that $L$ is not regular.

$\endgroup$
3
  • $\begingroup$ The question is about context-free languages. You show it is not regular. $\endgroup$ Oct 27 '14 at 9:48
  • $\begingroup$ Ah– I missed that. You have been right all along. $\endgroup$ Oct 27 '14 at 14:35
  • $\begingroup$ This is still a valid proof if you note that any context-free language over a 1-symbol alphabet must be regular, like Rick Decker stated above. $\endgroup$
    – Sid
    Oct 30 '15 at 14:55

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