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$ – Josh Hibschman May 20 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$ – Yuval Filmus May 20 at 18:43
  • 1
    $\begingroup$ Are there any counterexamples not involving a union? $\endgroup$ – Josh Hibschman May 20 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$ – Josh Hibschman May 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.