# Number of states in DFA equivalent to given NFA

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

• This depends on how you convert it to a DFA. – 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).