1
$\begingroup$

So i was reading a post on Minimum pumping length of regular language where Yuval Filmus has proved that a pumping lemma might have lesser number of states than a minimal DFA. But What about NFA's? Are NFA's able to give us minimum pumping length?

For example say we have a language L= $(10)^∗$, though for this minimal DFA will have $3$ states but NFA will have only $2$ states, which in fact is the pumping length of the language. So are NFA's able to give us exact pumping length of a language?

$\endgroup$
1
$\begingroup$

Here is a counterexample. Consider the language $L = 1^* + 0^*1^n$. The minimal NFA for $L$ has $n+C$ states for some constant $C$, but every word can be pumped, so the pumping length is 1.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks..got it.. :) $\endgroup$ – Turing101 Oct 24 '19 at 9:02

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.