# Minimum Pumping Length.

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.

## 1 Answer

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.

• Based on that reasoning would the minimum pumping length for 1011 be 5, since the minimal dfa has 5 states. – user283591 Nov 1 '15 at 23:47
• @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. – Brian M. Scott Nov 1 '15 at 23:52
• @justin: It’s the minimum length with the property that every word of that length (or more) can be decomposed and pumped. – Brian M. Scott Feb 12 '16 at 18:00
• @justin: The pumping lemma deals only with words that are in the language and are at least as long as the pumping length. – Brian M. Scott Feb 24 '16 at 6:20
• @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. – Brian M. Scott Feb 29 '16 at 21:30