# NFA and DFA storage cost

A theoretical worst case study shows that a single regular expression of length $n$ can be expressed as an NFA with $O(n)$ states. When the NFA is converted into a DFA, it may generate O($\Sigma^n$) states. The processing complexity for each character in the inpuyt it $O(1)$ in a DFA, but is $O(n^2)$ for an NFA when all $n$ states are active at the same time.

Please explain how NFA has at its maximum just $n$ states and its equivalent DFA has at most $O(\Sigma^n)$ states?

• Which paper is that? What did you not understand in the proofs?
– Raphael
Oct 4, 2013 at 6:41

Consider the construction of an NFA from a regular expression $r$. The construction is by induction over the generating sequence of $r$. If you examine the different operations (union, Kleene star, and concatenation), you will see that each operation increases the size of the NFA by a linear blowup.
For example, an NFA for $r_1\cup r_2$ is obtained by nondeterministically starting in an NFA for $r_1$ or an NFA for $r_2$, so the size of the NFA is (by induction) at most $|r_1|+|r_2|$.
Now, determinizing an NFA with $k$ states may involve a blowup of up to $2^k$ states. However, the NFA you obtained from the construction has $k=O(n)$ states, so the blowup is $2^{O(n)}$. The paper you read shows that the $O(n)$ factor is in fact $n\cdot O(\log|\Sigma|)$, thus making the total size $O(|\Sigma|^n)$.
• Of course, all the $O$s do not give the full picture. What is interesting is that these bounds are tight (are they?).
• The best lower bound I know for determinization is $2^{n/2}$ over an alphabet of size 2. I am not familiar with lower bounds for translation from a regular expression. Oct 4, 2013 at 9:38