Understanding the application of the pumping lemma to show that $L=\{0^{2^p}, p \geq 0\}$ is not regular

Question

I want to understand how is this proof working.

What I know:

Pumping lemma for regular language-:

Let $L$ be regular language. Then there exists a constant $n$ which depends on $L$ such that for every string $w \in L$ with $|w|\geq n$ and $w=xyz$ such that-:

1. $y\neq \epsilon$

2. $|xy| \leq n$

3. For all $i \geq 0$, $xy^iz \in L$

The proof that I am trying to understand: prove that $L=\{0^{2^p}, p \geq 0\}$ is not regular.

Solution:

1. Assume $L$ is regular. (I understand this).

2. $w=0^{2^n}=xyz$

3. $|y|$ can be from $1$ to $n$ (let) assuming $x=\epsilon$

4. Here we want to prove $xy^iz \not\in L$

So what the author has done is that:

|$xy^2z|=|xyz|+|y|$

The length of $xy^2z$ ranges from $2^n$ and $2^{n+1}$ But for $xy^2z$ $\in L$, we need its length in the multiple of $2^n$. This is what I understand. But I want to understand this better so that I can use this same problem solving ability to solve as many problems. Please review me.

What is the pumping length here? $i$ or $n$?

Answer 1

The pumping length here is what you refer to with the variable $n$. (Usually but not always, the letter $p$ is used, but the name is not important as long as it is clear to you and your audience.)

The meaning of the pumping length $n$ is that for a language to have the pumping property, we only require that strings of at least $n$ characters have the necessary $xyz$ partition. This is because it's always possible to construct an automaton that accepts arbitrarily complex string patterns but only up to any fixed length. We want to say sufficiently long strings of a regular language must have some repeatable segment.

(Note: since we don't care if strings shorter than the pumping length can be "pumped" or not, and the pumping length does only specifies the minimum length of strings we require to have a legal $xyz$ partition, there actually exists an infinite number of pumping lengths for each regular language)

For this proof in particular, we've picked the string $w = 0^{2^n}$: that is, $w$ consists of $2^n$ repetitions of the symbol $0$. Since $|w| \geq n$, the string is clearly long enough. Then you correctly note that following the rules of the $xyz$ partition, $y$ must consist of at least $1$, at most $n$ repetitions of $0$. The next-longest string in $L$ after $w$ is $0^{2^{n+1}}$, but as $|y| \leq n$, we can reach at most $0^{2^{n}+n}$. Therefore $xy^2z$ is, no matter the choice of $y$ not in $L$ and therefore we've disproved $L$ having the pumping property. Since all regular languages have the property, $L$ is not regular.

Answer 2

We want to show the language $L = \{0^{2^n}: n \ge 0\}$ is nonregular.

By way of contradiction, suppose $L$ is regular. Then, there exists an integer $p$, called the pumping length, such that all strings in $L$ of length at least $p$ can be pumped. Let $w=0^{2^p}$. Because $|w| \ge p$, by the pumping lemma, there exists a partition $w=xyz$ such that $|xy| \le p, 1 \le |y| \le p$ and $xy^iz \in L, \forall i \ge 0$. The length of $xyyz$ is at least $2^p +1$ and at most $2^p + p < 2^p + 2^p = 2^{p+1}$, whence $xyyz \notin L$, a contradiction.