# Minimal DFA with more states than its equivalent NFA

I understand that using a bad case for subset construction as provided through an example in the book - Introduction to Automata Theory, Languages and Computation, we can definitely have an NFA with $n+1$ states, and get a corresponding minimal DFA with $2^n$ states due to the power set logic.

But, my question is, is there a case where you can have an NFA (with or without epsilon moves), with $n$ states, having an equivalent minimal DFA of $p$ states, where $p \neq 2^n \ and \ p > 2n$ ?

• Oh, wait. The 3am dragon is not yet slain. The example you give in your first paragraph is an NFA with $n$ states whose minimal DFA has $p=2^{n-1}$ states. That satisfies $p\neq 2^n$ and, for large enough $n$ ($n>4$) $p>2n$. So is that already an answer or did you mean to write some other condition? – David Richerby Mar 5 '18 at 9:43
• @DavidRicherby Hahaha. The given language in the book is the set of all strings in $\{0,1\}^*$ such that the $n^{th}$ symbol from the end is a 1. There are n+1 states for the corresponding NFA for this language, and it is given that the said NFA can have no equivalent DFA with lesser than $2^n$ states. This is the example I gave in the first paragraph. – Vishhvak Srinivasan Mar 5 '18 at 10:15
• @DavidRicherby What I basically want is a case where an NFA can have lesser states (say it has P states) than its minimal DFA (say it has Q states)) equivalent by a margin such that the ratio $P/Q < 1/2$. I know that the bad case for subset construction results in exponential growth of states ($i.e, 2^n$ states), but I am interested in cases where the growth is not $2^n$, but a random number maybe? Any specific example would suffice. – Vishhvak Srinivasan Mar 5 '18 at 10:21

Consider the language $(0+1)^*0(0+1)^{n-1}$ over the alphabet $\{0,1,2\}$. It is accepted by an NFA having $n+1$ states, and its minimal DFA contains $2^n+1$ states.

• This doesn't seem to work for me? The corresponding DFA, for $n = 3$ using subset construction itself gives me $2^n$ states, and the same for the minimal DFA equivalent as well, obviously. – Vishhvak Srinivasan Mar 5 '18 at 17:52
• When $n=0$ you need three states, corresponding to $(0+1)^*0,\epsilon + (0+1)^*1,\Sigma^*2\Sigma^*$. Are you considering the fact that the alphabet also contains 2? – Yuval Filmus Mar 5 '18 at 22:55

Yes there is. When converting an NFA with $n$ states to a DFA you are going to have more states in the DFA then you did in the NFA but typical the DFA has less than $2^n$ states.

Consider the NFA the accepts the strings $\{aaa,aab\}$. If you convert that NFA to a DFA you will find that the DFA has less than 8 states.

• @Bob Sincere Apologies. Edited my question. I'm looking for a case where the minimal DFA ends up having MORE number of states than the given NFA we take. – Vishhvak Srinivasan Mar 5 '18 at 6:38

I happened to find an example, with lots of trial and error throughout the day, where p = 12 and n = 5. You can take a look below. Although the Minimal DFA turned out a bit messy. Will update this answer incase I find a generic idea on how to come up with such examples, or an intuition behind this idea.  • In case there is something wrong in my example, please do not hesitate to point out or edit as you please. Thank you! – Vishhvak Srinivasan Mar 5 '18 at 12:59