Does a minimal DFA with k states imply that there couldn't exist a NFA with less than k states?

Question

Does a minimal DFA with k states imply that there couldn't exist a NFA with less than k states?

I was wondering if you could have a NFA with less than k states that generates the same language as a minimal DFA with k states?

Answer 1

No. Quite the opposite. In fact, it's possible to find NFAs with $n$ states whose minimal DFA has $\approx 2^n$ states, and this exponential blow-up is expected. It's highly uncommon for a minimal DFA to be of roughly the same size as a minimal NFA for the same language.

For instance, consider the language in the alphabet $\{a,b\}$ of words whose $3$rd to last letter is an $a$. It's easy to find a small NFA which solves the problem:

But a corresponding DFA must have at least $8$ states (do you see why?).

See here for a more in depth discussion, and here for a proof that the DFA for this particular example really does require exponentially many states compared to the NFA.

---

I hope this helps ^_^