# Minimum pumping length of regular language

I know the method to the find the minimum pumping length of regular language by constructing minimal DFA and finding the number of states but I am not able to quite understand why is it working.

For example, $L = (10)^*$. Here minimum pumping length is 1 by constructing DFA. But by pumping lemma, how can there be a string of length 1 belonging to $L$? As pumping lemma says the string $S$ should be such that $|S| \le p$ and $S$ should belong to $L$, where $p$ is the pumping length, and here there is no string of length 1 belonging to $L$.

Your example in fact demonstrates that the pumping length can be smaller than the number of states in the minimal DFA. In your case the minimal DFA contains 3 states, but the pumping length is 2.

The pumping length of a language $L$ is the minimal $p$ such that every word $w \in L$ of length at least $p$ can be written as $w = xyz$, where $|xy| \leq p$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$.

If $L$ contains no words of length $p$ that's not problematic at all. For example, the pumping length of $\{ w \}$ is $|w|+1$. In that case the pumping property holds vacuously.

• The answer was minimum pumping length can be atmost 2 and minimum 1. So 1 was the answer and not 2. And yes for finite languages, I know pumping length is |W| + 1. Can you please tell how can it be 1? – Sagar P Nov 27 '17 at 20:01
• The minimum pumping length is a single number. It's either 1 or 2. According to my definition, it is 2 rather than 1. Perhaps you're using a different definition which doesn't require $|xy| \leq p$. – Yuval Filmus Nov 27 '17 at 20:02
• When we find the minimum pumping length using minimal DFA, the answer is longest path from initial state without a cycle right ? So even with minimal DFA, the answer comes out to be 1. – Sagar P Nov 27 '17 at 20:03
• It really depends on the definition of "minimum pumping length". I have given my definition. What is yours? – Yuval Filmus Nov 27 '17 at 20:04
• The one is wikipedia which is same as yours. Even my textbook uses the same. – Sagar P Nov 27 '17 at 20:06