Can a nondeterministic finite automata (NDFA) be efficiently converted to a deterministic finite automata (DFA) in subexponential space/time? Twenty years ago, I built an regular expression package that included conversions from regular expressions to a finite state machine (DFA) and supported a host of closed regular expression  operations (Kleene star, concatenation, reverse, set operations, etc). I was unsure about the worst case performance of my package.

A DFA has the same expressive power as an NDFA, because an n-state NDFA can be trivially converted to a DFA having 2^n states. However, are there any lower upper bound guarantees for such a conversion that do not require an exponential explosion in state?

I was unable to come up with examples mal-behaving regular expressions or NDFAs, but I didn't spend much time thinking about it. I am guessing a regular expression like ((((e|A|B|C)*(e|D|E|F))*(e|G|H|I))*(e|J|K|L|M))* which mixes a lot of alternations and Kleene stars would have a linearly sized NDFA but an expansive DFA.
It is known that for every pair of naturals numbers n,a such that n &lt;= a &lt;= 2^n, there exists a minimal NDFA with n states whose corresponding equivalent minimal dfa has a states (over a four letter alphabet).

See the paper here: Deterministic blow-ups of minimal nondeterministic finite automata over a fixed alphabet.

Abstract of the paper:


  We show that for all integers n and α
  such that n ≤ α ≤ 2^n, there exists a
  minimal nondeterministic finite
  automaton of n states with a
  four-letter input alphabet whose
  equivalent minimal deterministic
  finite automaton has exactly a states.
  It follows that in the case of a
  four-letter alphabet, there are no
  "magic numbers", i.e., the holes in
  the hierarchy. This improves a similar
  result obtained by Geffert for a
  growing alphabet of size n + 2 (Proc.
  7th DCFS, Como, Italy, 23-37).


So, I suppose the answer to your question is, no.