0
$\begingroup$

Michael Sipser offers the definition:

The pumping lemma says that every regular language has a pumping length p, such that every string in the language can be pumped if it has length p or more. If p is a pumping length for language A, so is any length p′ ≥ p. The minimum pumping length for A is the smallest p that is a pumping length for A.

Now, (01)* in set notation is {€, 01,0101,010101....} Taking minimum pumping length = 1, according to the definition, we have the statement if a string in the language has length 1 or more, it can be pumped.

This statement is true for all elements of the above mentioned set, so can the minimum pumping length be 1?

p.s. the minimum pumping length for (01)* has been asked here before but it doesn't answer my doubt that since the condition holds for minimum pumping length = 1, why is it not the answer?

$\endgroup$
  • 1
    $\begingroup$ You probably refer to this answer: What is the minimal pumping length of this string (01)∗ by Yuval. As explained there, the pumping length does not only give the minimal length of the string, but also restricts the length of the pumped part of the string. You cannot pump 01 in (01)* using only a single letter. $\endgroup$ – Hendrik Jan Jun 30 at 14:01
  • $\begingroup$ "the minimum pumping length for (01)* has been asked here". Where is here? Please edit the question to include an explicit reference instead of say "here". (This comment will be deleted upon feedback.) $\endgroup$ – John L. Jun 30 at 15:41
  • $\begingroup$ "say 'here'" should have been "here" in my last comment. $\endgroup$ – John L. Jun 30 at 15:53
1
$\begingroup$

The minimum pumping length $\ell$ of $(01)^*$ is $2$.

First of all notice that there are no words of length $1$ in the language. Then, if you look at a formal definition of the pumping lemma for regular languages (what you wrote is still informal) you'll find that the length $|xy|$ of the prefix $xy$ of a word in the language that can be pumped must be $\le \ell$.

This allows you to prove that the minimum pumping length $\ell$ must be $2$ by showing:

  • That there is a DFA for $(01)^*$ that uses at most $2$ states, implying $\ell \le 2$. This DFA is trivial to obtain.
  • That $\ell=1$ is not a valid pumping length. This is true since $|y|$ must be positive and, together with $|xy| \le \ell$, this implies $|y|=1$. In other words $x = \epsilon$ and $y=0$. It is easy to obtain a word not in the language by repeating $y$ either $0$ or at least $2$ times.
| cite | improve this answer | |
$\endgroup$

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