Let's say there is a NFA with $n$ states with an alphabet consisting of $x$ symbols. I convert it to an equivalent DFA. Can I say that the number of states in the equivalent DFA is $x^n$?

  • 1
    $\begingroup$ This depends on how you convert it to a DFA. $\endgroup$ – Yuval Filmus Dec 1 '18 at 21:44

The standard powerset construction takes an NFA with $n$ states over an arbitrary alphabet and produces a DFA with $2^n$ states; this is tight for alphabets containing at least two symbols (see Chrobak's paper below for several references for this).

As for unary alphabets, Chrobak showed in his paper Finite automata and unary languages that a unary NFA with $n$ states can be converted to a unary DFA with $O(e^{\sqrt{n\log n}})$ states, and showed that this is tight (up to the hidden constant factor).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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