3
$\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$
0
3
$\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.

$\endgroup$
8
  • $\begingroup$ Thanks..got it.. :) $\endgroup$
    – Turing101
    Oct 24 '19 at 9:02
  • $\begingroup$ Is $L = 1^* + 0^*1^n$ equivalent to $𝐿=1^+0^*1^𝑛$? i.e. matches words that begin with 1 end with a $1^n$? The notation in Sipser's book is a little different. $\endgroup$ May 20 '21 at 18:42
  • 1
    $\begingroup$ The language $L$ consists of all words of the form $1^a$ or $0^a1^n$, for arbitrary $a \in \mathbb{N}$ (including $a = 0$). $\endgroup$ May 20 '21 at 18:43
  • 1
    $\begingroup$ Are there any counterexamples not involving a union? $\endgroup$ May 20 '21 at 21:21
  • 1
    $\begingroup$ @YuvalFilmus I like your solution :D I was curious whether a union was the only way to achieve p < min DFA states. However, I found one without a union! It seems $L=0^*1^*$ is a 3 state DFA where $p=1$. $\endgroup$ May 21 '21 at 21:16

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.