16
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are there any restrictions on the class of NFAs that you would want to accept as input? Some restrictions lead to better upper bounds. $\endgroup$ – András Salamon Aug 17 '10 at 1:52
  • $\begingroup$ not a very important point, but need ndfa be its own tag? $\endgroup$ – Lev Reyzin Aug 18 '10 at 15:47
  • $\begingroup$ Yes there are restrictions. The NFAs are constructed directly from regular expressions by treating them as generalized transition graphs. seas.upenn.edu/~cit596/notes/dave/regexp-nfa4.html $\endgroup$ – Wesner Moise Aug 18 '10 at 16:37
15
$\begingroup$

It is known that for every pair of naturals numbers n,a such that n <= a <= 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.

$\endgroup$
  • $\begingroup$ the question is asking for an "algorithm" running in subexponential time and space for converting the NFA. $\endgroup$ – Marcos Villagra Aug 17 '10 at 1:39
  • $\begingroup$ @Marcos: If your output is exponential, you cannot possibly have an algorithm that runs in sub-exponential time. $\endgroup$ – Aryabhata Aug 17 '10 at 1:40
  • 1
    $\begingroup$ This is a general result. If there are known restrictions on the class of input NFAs, then it might be possible to do better. $\endgroup$ – András Salamon Aug 17 '10 at 1:50
  • $\begingroup$ @Andras: Agreed, but given that this is probably programming related (which will support Kleen * etc), I doubt if the set of input NFA will be restricted to a proper subset. $\endgroup$ – Aryabhata Aug 17 '10 at 1:55
  • 5
    $\begingroup$ This result was recently strengthened to use a three letter alphabet, and the constructions are a bit simpler: portal.acm.org/… $\endgroup$ – Matt Maly Aug 18 '10 at 5:11
13
$\begingroup$

The classic example for a language with an exponential separation between DFA size and NFA size is the following finite language: binary strings of length exactly 2n in which the first half is not equal to the second half. A NFA would guess an index i in which the first and second half disagree. A lower bound for a DFA follows from communication complexity, for example.

$\endgroup$
8
$\begingroup$

The minimum DFA corresponding to an NFA has 2^n states in the worst case, so you can't garantee anything. Without having a constructive example, the reasoning is that in an NFA you can be at any arbitrary subset of states after reading a certain input string, and each such subset might behave differently when observing one character. Suppose a language with two characters in the alphabet (a and b), and an NFA N with n states that starts with an accepting state at s_0. Now enumerate all subsets of states of N, and build the transition table such that observing "a" from subset S_i takes you to subset S_i+1 and observing b takes you to subset S_i-1 (this is doable for some enumerations, I think). Now this automata has n states and accepts sequences of m a's and n b's such that m-n = 0 mod 2^|N|, and cannot be expressed with a DFA that has less than 2^|N| states (since it might need to cycle through all subsets of states of the NFA N).

$\endgroup$
  • $\begingroup$ Can this be turned into an argument that says "if (some bad thing) is avoided in the NFA, then the DFA has subexponential number of states"? $\endgroup$ – András Salamon Aug 17 '10 at 1:54
  • 1
    $\begingroup$ @András, yes. "If nondeterminism is avoided in the NFA, then the DFA has subexponential number of states". $\endgroup$ – P Shved Aug 17 '10 at 7:12
  • 2
    $\begingroup$ Pavel, yes, obviously. Is there any non-trivial property that can be recognized efficiently which also guarantees subexponential blowup? $\endgroup$ – András Salamon Aug 17 '10 at 17:21

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.