1
$\begingroup$

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$ ?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – David Richerby
    Mar 5, 2018 at 9:43
  • $\begingroup$ @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. $\endgroup$
    – Vishhvak Srinivasan
    Mar 5, 2018 at 10:15
  • $\begingroup$ @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. $\endgroup$
    – Vishhvak Srinivasan
    Mar 5, 2018 at 10:21

3 Answers 3

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Vishhvak Srinivasan
    Mar 5, 2018 at 17:52
  • $\begingroup$ 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? $\endgroup$
    – Yuval Filmus
    Mar 5, 2018 at 22:55
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @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. $\endgroup$
    – Vishhvak Srinivasan
    Mar 5, 2018 at 6:38
0
$\begingroup$

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.

NFA

enter image description here

Improve this answer
$\endgroup$
1
  • $\begingroup$ In case there is something wrong in my example, please do not hesitate to point out or edit as you please. Thank you! $\endgroup$
    – Vishhvak Srinivasan
    Mar 5, 2018 at 12:59

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.