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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks..got it.. :) $\endgroup$
    – Turing101
    Oct 24, 2019 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, 2021 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, 2021 at 18:43
  • 1
    $\begingroup$ Are there any counterexamples not involving a union? $\endgroup$
    – Josh Hibschman
    May 20, 2021 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, 2021 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.