Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
In some paper I read,
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?
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)$.
