2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Sagar P Nov 27 '17 at 20:01
  • $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Nov 27 '17 at 20:02
  • $\begingroup$ 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. $\endgroup$ – Sagar P Nov 27 '17 at 20:03
  • $\begingroup$ It really depends on the definition of "minimum pumping length". I have given my definition. What is yours? $\endgroup$ – Yuval Filmus Nov 27 '17 at 20:04
  • $\begingroup$ The one is wikipedia which is same as yours. Even my textbook uses the same. $\endgroup$ – Sagar P Nov 27 '17 at 20:06

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.