2
$\begingroup$

As title says, can the number of states in DFA be greater than $2^n$ when language-equivalent NFA has $n$ states - that is if the NFA recognizes the same language as the DFA and has $n$ states, can DFA have more than $2^n$ states?

I think it is, and this is trivially. However Wikipedia seeems to write that it is not possible to have more than $2^n$ states. So comes the question.

$\endgroup$

closed as unclear what you're asking by D.W., David Richerby, Nicholas Mancuso, Juho, Rick Decker Feb 8 '15 at 19:47

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ The person asking you the question probably means pairs $(A, f(A))$ where $f$ is the powerset construction for determinising NFA. $\endgroup$ – Raphael Feb 6 '15 at 8:01
  • $\begingroup$ The $2^n$ bound is for the minimal DFA. Of course you can increase the size arbitrarily by duplicating the set of states. $\endgroup$ – Klaus Draeger Feb 6 '15 at 13:43
  • $\begingroup$ Where does Wikipedia say that? Please provide a link and a quote. I suspect you are misunderstanding Wikipedia and your question is based on a faulty premise and a too-fast reading of what Wikipedia actually says. $\endgroup$ – D.W. Feb 6 '15 at 23:04
4
$\begingroup$

it surely can, but it needs not. Using the powerset construction you can convert any $n$-state NFA into a DFA with at most $2^n$ states.

$\endgroup$
  • $\begingroup$ @Juho My guess is the OP copied the question wrong. $\endgroup$ – Raphael Feb 6 '15 at 8:01
  • $\begingroup$ @Juho, it should answer the question. Starting from an NFA with n states, The MINIMAL equivalent DFA will have at most $2^n$, but an arbitrary DFA that accepts the same language may have more (redundant, useless) states. $\endgroup$ – Ran G. Feb 6 '15 at 14:08

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