0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Which paper is that? What did you not understand in the proofs? $\endgroup$ – Raphael Oct 4 '13 at 6:41
5
$\begingroup$

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)$.

$\endgroup$
  • 1
    $\begingroup$ Of course, all the $O$s do not give the full picture. What is interesting is that these bounds are tight (are they?). $\endgroup$ – Raphael Oct 4 '13 at 6:40
  • $\begingroup$ 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. $\endgroup$ – Shaull Oct 4 '13 at 9:38

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.