1
$\begingroup$

I was trying to use the pumping lemma to prove that the language, $ \{ 0^N | \ n $ is a power of 2$ \}$, is not regular.

Assume to the contrary that the language is regular. Let p be the pumping length given by the pumping lemma and let $s = 0^{2^p}$. As $|s| \ge p$, the pumping lemma guarantees we can split s into three pieces $x, y, z$ such that $ y \ne $ empty string, $|xy| \le p$ and $xy^iz \in$ the language.

From the conditions of the pumping lemma, we know y contains between one and $p$ zeros. In the case that $i=2$, the length of $xyyz$ is between $0^{2^p} + 1$ and $0^{2^p} + p$. However, to get to the next power of 2 after $0^{2^p}$, we need $0^{2^p + 1}$.

I wanted to prove the bounds of $|xyyz|$ are less than the $0^{2^{n+1}}$. To do this I began writing an inductive proof to show that $0^{2^n} + n < 0^{2^{n+1}}$ for $n \ge 1$.

Basis: $n=1$

$0^{2^1} + 1 \rightarrow$ length is $3$

$0^{2^{1 + 1}} \rightarrow 0^{2^2} \rightarrow$ length is $4$

Induction: assume the statement is true for all $n \le k$. Lets do the case for $n = k + 1$

$ 0^{2^{k+1}} + k + 1 = 0^{2^k \cdot 2} + k + 1$

$0^{2^{k + 1 +1}} = 0^{2^k \cdot 2 \cdot 2}$

This is where I get stuck. I can see very clearly that $0^{2^k \cdot 2 \cdot 2}$ is greater than $0^{2^{k+1}}$, but I don't see how its greater than $ 0^{2^{k+1}} + k + 1$

$\endgroup$
3
  • 1
    $\begingroup$ Off-topic: When I saw the title I thought "Oh my lord that guy wrote $0^{2^n}$ and $0^{2^{n+1}}$ in a inequation, it's nonsense", and then when I entered I realized what he was up to. $\endgroup$
    – manooooh
    Commented Apr 18, 2018 at 0:35
  • $\begingroup$ @manooooh good point, I'll edit the title $\endgroup$
    – maddie
    Commented Apr 18, 2018 at 0:45
  • $\begingroup$ I take it that by O you actually mean $\mathcal{O}$ $\endgroup$ Commented Apr 18, 2018 at 1:22

1 Answer 1

0
$\begingroup$

First of all, "I began writing an inductive proof to show that $0^{2^n} + n < 0^{2^{n+1}}$ for $n≥1$" is definitely inaccurate since you can't add a string to a number. You are trying to show the length of string satisfies that condition, as your title said.

Then you only need to prove $2^n > n$, which can be easily solved by calculus or induction. Anyway, the problem in your proof is that you didn't focus on string's length.

$\endgroup$
2
  • $\begingroup$ This seems more like a comment, you may want to do that instead of posting this as an answer $\endgroup$ Commented Apr 18, 2018 at 1:23
  • $\begingroup$ @AhmedMasud unfortunately I don’t have the privilege to do that ;( $\endgroup$
    – Wenzel
    Commented Apr 18, 2018 at 1:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .