# Are number of states in a NFA same as Pumping length?

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?

## 1 Answer

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.

• Thanks..got it.. :) – Turing101 Oct 24 '19 at 9:02
• 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. – Josh Hibschman May 20 at 18:42
• 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$). – Yuval Filmus May 20 at 18:43
• Are there any counterexamples not involving a union? – Josh Hibschman May 20 at 21:21
• @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$. – Josh Hibschman May 21 at 21:16