2
$\begingroup$

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$?

$\endgroup$
4
  • $\begingroup$ Hello supcem, I cleared up the notation and phrasing of your post a bit. Please review that I did not change the intent of your question. Thank you :) $\endgroup$
    – kviiri
    Nov 12, 2021 at 10:59
  • $\begingroup$ Your statement of the pumping lemma says: for every string w of length at least n and w=xyz. This is incorrect, it should state: for every string w of length at least n, there exists a partition w=xyz... There's a difference between stating something holds for every partition versus something holds for at least one partition. $\endgroup$ May 12, 2022 at 5:00
  • $\begingroup$ The pumping length is n in your statement of the problem. Normally, the variable $p$ is used, so I'll give the proof below using the variable $p$. $\endgroup$ May 12, 2022 at 5:01
  • $\begingroup$ The best way to understand this proof method is to work through the proof of the pumping lemma (see Sipser's text), to see why the pumping length refers to the number of states of the DFA, and to understand how the pigeonhole principle guarantees there exists a partition $w=xyz$ satisfying those conditions. $\endgroup$ May 12, 2022 at 5:02

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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