<p>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.</p>

CC BY-SA 4.0
2021-11-09T18:33:09.613Z
Another maybe simpler example is "the n-th character before the end of the word is an $a$". Can be done with $n+1$ states with an NFA that guesses when the end of the word occurs, whereas a DFA clearly needs to have $2^n$ states as each of the possible states of the $n$ last characters define a different set of continuations that make the automaton accept.
Antoine Amarilli 'a3nm'
CC BY-SA 2.5
2010-08-17T17:14:07.217Z
2010-08-17T17:14:07.217Z
Noam
<p>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).</p>

CC BY-SA 2.5
2010-08-17T01:54:10.763Z
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"?
András Salamon
CC BY-SA 2.5
2010-08-17T07:12:29.600Z
@András, yes.  "If nondeterminism is avoided in the NFA, then the DFA has subexponential number of states".
P Shved
CC BY-SA 2.5
2010-08-17T17:21:42.743Z
Pavel, yes, obviously.  Is there any non-trivial property that can be recognized efficiently which also guarantees subexponential blowup?
András Salamon
CC BY-SA 2.5
2010-08-17T01:28:14.353Z
2010-08-17T01:34:06.180Z
2010-08-17T01:34:06.180Z
Alexandre Passos
<p>It is known that for every pair of naturals numbers <code>n,a</code> such that <code>n &lt;= a &lt;= 2^n</code>, there exists a minimal NDFA with <code>n</code> states whose corresponding equivalent minimal dfa has <code>a</code> states (over a four letter alphabet).</p>

<p>See the paper here: <a href="http://portal.acm.org/citation.cfm?id=1770337&amp;dl=GUIDE&amp;coll=GUIDE&amp;CFID=100818292&amp;CFTOKEN=24447810">Deterministic blow-ups of minimal nondeterministic finite automata over a fixed alphabet</a>.</p>

<p>Abstract of the paper:</p>

<blockquote>
  <p>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).</p>
</blockquote>

<p>So, I suppose the answer to your question is, no.</p>

CC BY-SA 2.5
2010-08-17T01:39:09.130Z
the question is asking for an "algorithm" running in subexponential time and space for converting the NFA.
Marcos Villagra
CC BY-SA 2.5
2010-08-17T01:40:50.530Z
@Marcos: If your output is exponential, you cannot possibly have an algorithm that runs in sub-exponential time.
Aryabhata
CC BY-SA 2.5
2010-08-17T01:50:39.790Z
This is a general result.  If there are known restrictions on the class of input NFAs, then it might be possible to do better.
András Salamon
CC BY-SA 2.5
2010-08-17T01:55:44.490Z
@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.
Aryabhata
CC BY-SA 2.5
2010-08-17T01:21:53.837Z
2010-08-17T01:21:53.837Z
Aryabhata
<p>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.</p>

<p>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?</p>

<p>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. </p>

CC BY-SA 2.5
2010-08-17T01:52:27.603Z
Are there any restrictions on the class of NFAs that you would want to accept as input?  Some restrictions lead to better upper bounds.
András Salamon
CC BY-SA 2.5
2010-08-18T15:47:12.413Z
not a very important point, but need ndfa be its own tag?
Lev Reyzin
CC BY-SA 2.5
2010-08-18T16:37:58.287Z
Yes there are restrictions. The NFAs are constructed directly from regular expressions by treating them as generalized transition graphs. http://www.seas.upenn.edu/~cit596/notes/dave/regexp-nfa4.html
Wesner Moise
<dfa><regular-expressions><bounds>
Can a nondeterministic finite automata (NDFA) be efficiently converted to a deterministic finite automata (DFA) in subexponential space/time?
Wesner Moise
# Can a nondeterministic finite automata (NDFA) be efficiently converted to a deterministic finite automata (DFA) in subexponential space/time?

(Asked by: username_0 on 2010-08-17)

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.

**Tags:** dfa, regular-expressions, bounds
> **Comments:**
> **username_1**: Are there any restrictions on the class of NFAs that you would want to accept as input?  Some restrictions lead to better upper bounds.  
> **username_2**: not a very important point, but need ndfa be its own tag?  
> **username_0**: Yes there are restrictions. The NFAs are constructed directly from regular expressions by treating them as generalized transition graphs. http://www.seas.upenn.edu/~cit596/notes/dave/regexp-nfa4.html  

---

## 3 answers

### Answer by username_7 on 2010-08-17. Score: 16 | Accepted answer

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](http://portal.acm.org/citation.cfm?id=1770337&dl=GUIDE&coll=GUIDE&CFID=100818292&CFTOKEN=24447810).

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.

> **Comments:**
> **username_8**: the question is asking for an "algorithm" running in subexponential time and space for converting the NFA.  
> **username_7**: @Marcos: If your output is exponential, you cannot possibly have an algorithm that runs in sub-exponential time.  
> **username_1**: This is a general result.  If there are known restrictions on the class of input NFAs, then it might be possible to do better.  
> **username_7**: @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.  

---

### Answer by username_3 on 2010-08-17. Score: 14

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.

> **Comments:**
> **username_4**: Another maybe simpler example is "the n-th character before the end of the word is an $a$". Can be done with $n+1$ states with an NFA that guesses when the end of the word occurs, whereas a DFA clearly needs to have $2^n$ states as each of the possible states of the $n$ last characters define a different set of continuations that make the automaton accept.  

---

### Answer by username_5 on 2010-08-17. Score: 8

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

> **Comments:**
> **username_1**: 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"?  
> **username_6**: @András, yes.  "If nondeterminism is avoided in the NFA, then the DFA has subexponential number of states".  
> **username_1**: Pavel, yes, obviously.  Is there any non-trivial property that can be recognized efficiently which also guarantees subexponential blowup?  

---

