1
$\begingroup$

What is the minimum pumping length of $(01)^*$

The solutions says 1, but can someone explain why that is? I understand this language accepts the empty string, but the minimum pumping length cannot be $0$. But, why is it 1? A general explanation of how to calculate the minimum pumping length would be much appreciated as well.

Thanks.

$\endgroup$
1
$\begingroup$

Look at the minimal DFA for $(01)^*$: it has three states(one garbage or dead state), so any non-empty word of the language must cause it to repeat a state and therefore can be pumped. The minimum length of a non-empty word of the language is $2$, so the minimum pumping length is at most $2$. Note, though, that the language contains no word of length $1$, so if $w$ is in the language, and $|w|\ge 1$, then automatically $|w|\ge 2$, and $w$ can be pumped. Thus, $1$ is also a pumping length for the language.

$\endgroup$
  • $\begingroup$ Based on that reasoning would the minimum pumping length for 1011 be 5, since the minimal dfa has 5 states. $\endgroup$ – user283591 Nov 1 '15 at 23:47
  • 1
    $\begingroup$ @user283591: You mean for the one-word language $\{1011\}$? The minimum DFA actually has six states. However, the minimum pumping length is indeed $5$, since $1011$ cannot be pumped. $\endgroup$ – Brian M. Scott Nov 1 '15 at 23:52
  • 1
    $\begingroup$ @justin: It’s the minimum length with the property that every word of that length (or more) can be decomposed and pumped. $\endgroup$ – Brian M. Scott Feb 12 '16 at 18:00
  • 1
    $\begingroup$ @justin: The pumping lemma deals only with words that are in the language and are at least as long as the pumping length. $\endgroup$ – Brian M. Scott Feb 24 '16 at 6:20
  • 1
    $\begingroup$ @justin: I just did: if it had pumping length $1$, the word $a$ would be long enough to qualify for the pumping lemma. Thus, it could be decomposed as $xyz$, where $|xy|\le 1$ and $|y|\ge 1$. Obviously this means that $x=z=\epsilon$ and $y=a$. But then $y^k\in L$ for all $k\ge 0$, meaning that $a^k\in L$ for all $k\ge 0$. This is false, and $L$ is regular, so $1$ can’t be a pumping length for $L$. \\ It is languages that have pumping lengths, not individual strings. $\endgroup$ – Brian M. Scott Feb 29 '16 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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