19
$\begingroup$

All non-deterministic finite automata can be turned into equivalent deterministic finite automata. However, a deterministic finite automata only allows a single arrow per symbol pointing from a state. Therefore, its states should be members of the power set of states of the NFA. This seems to indicate that the number of states of the DFA could scale exponentially in terms of the number of states of the NFA. However, I was wondering how to actually prove this.

$\endgroup$

migrated from cstheory.stackexchange.com Oct 14 '12 at 13:49

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 7
    $\begingroup$ It's a reasonable question, and the construction isn't completely obvious, but it still might be a homework question. So, it would be helpful to hear why you want to know. $\endgroup$ – David Eppstein Sep 16 '12 at 5:07
  • $\begingroup$ theres some constructions here but it seems like it ought to be in a paper somewhere. dont know of a ref. also off top of my head think there is a construction such that the NFA counts in binary in its active states, and accepts only after about $2^n$ transitions...? $\endgroup$ – vzn Sep 16 '12 at 5:07
  • $\begingroup$ See also cs.stackexchange.com/questions/3381/… $\endgroup$ – Gilles Aug 29 '16 at 12:08
15
$\begingroup$

One operation that transforms an NFA into another NFA but does not do so for a DFA is reversal (point all the arrows the other way round, and swap initial states with accepting states). The language recognized by the transformed automaton is the reversed language $L^R = \{u_{n-1}\ldots u_0 \mid u_0\ldots u_{n-1} \in L\}$.

Thus one idea is to look for a language that has an asymmetric construction. Going forward, this language should be recognized by inspecting the first $n$ symbols, requiring only $n + O(1)$ states. Going backwards, it should be necessary to keep a memory of the last $n$ states, which requires $A^n + O(1)$ states where $A$ is the alphabet size.

We're looking for a language of the form $M_n S M'$ where $M_n$ consists of words of length $n$, $S$ is a nontrivial subset of the alphabet, and $M'$ doesn't provide any further constraint. We might as well pick the simplest alphabet $\mathscr{A} = \{a,b\}$ (a singleton alphabet won't do, you don't get smaller NFAs there) and $M' = \mathscr{A}^*$. A nontrivial $S$ means $S = \{a\}$. As for $M_n$, we require that it does not correlate with $S$ (so that the DFA for the reversed language will need to keep the memory of $S$): take $M_n = \mathscr{A}^n$.

Thus let $L_n = (a|b)^n a (a|b)^*$. It is recognized by a simple DFA with $n+2$ states.

dfa

Reversing it yields an NFA that recognizes $L_n^R = (a|b)^* a(a|b)^n$.

nfa

The minimal DFA that recognizes $L_n^R$ has at least $2^{n+1}$ states. This is because all the words of length $2^{n+1}$ must reach distinct states in the DFA. (In other words, they belong to distinct Myhill-Nerode equivalence classes.) To prove this, take two distinct words $u,v \in \mathscr{A}^{n+1}$ and let $k$ be a position where they differ ($u_k \ne v_k$). Without loss of generality, let's assume $u_k = a$ and $v_k = b$. Then $u b^k \in L_n^R$ and $v b^k \notin L_n^R$ ($b^k$ is a distinguishing extension for $u$ and $v$). If $u$ and $v$ led to the same state in a DFA recognizing $L_n^R$ then so would $u b^k$ and $v b^k$, which is impossible since one leads to an accepting state and the other one doesn't.

Acknowledgement: this example was cited in Wikipedia without explanations. The article gives a reference to an article that I haven't read which gives a tighter bound:
Leiss, Ernst (1981), "Succinct representation of regular languages by Boolean automata", Theoretical Computer Science 13 (3): 323–330, doi:10.1016/S0304-3975(81)80005-9.

$\endgroup$
  • $\begingroup$ Logical Answer: States in DFA are use as memory(to store some information like on-off fan switch), so what can be represent in single state in DFA can be represented using combination of states in equivalent NFA. That is the reason NFA has less states compared to equivalent DFA. Now if you have $n$ states in a set $Q$ then set of all possible combinations of $Q$ is power-set that is $2^n$, So if we reverse an NFA of $n$ states into equivalent DFA, then DFA will be consist of at most $2^n$ states. – Does it make sense? $\endgroup$ – Grijesh Chauhan Apr 9 '14 at 19:19
  • 1
    $\begingroup$ @GrijeshChauhan This isn't what the question asked. Yes, it's easy to see that for every NFA with $n$ states there is a DFA with at most $2^n$ states. But here we want to see that the bound is reached, i.e. that for any $n$ there is an $n$-state NFA such that the smallest equivalent DFA has at least $2^n$ states (or close thereto, here I prove the bound $2^{n-1}$). $\endgroup$ – Gilles Apr 9 '14 at 19:26
  • $\begingroup$ hmm... after reading your answer twice and from comment "But here we want to see that the bound is reached" now I could have understand. Thanks. $\endgroup$ – Grijesh Chauhan Apr 9 '14 at 19:30
8
$\begingroup$

Consider the following family of languages: $L_n = \{ x_1, x_2, \ldots, x_k \# x_{k+1}: \exists i \in \{1, \ldots, k\} \text{ with } x_i = x_{k+1} \}$

The alphabet of $L_n$ is $\{\#, 1,\ldots, n \}$.

There is an NFA with $O(n)$ states that recognizes the language $L_n$. It has $n$ copies. In the $i$th copy we guess that the last letter will be $i$, and check our guess. It's simple to construct such a copy with $3$ states. The only non-determinism is in the initial state.

However, there is no DFA that recognizes $L_n$ with less than $2^{O(n)}$ states because, intuitively, a DFA must remember subsets of $\{1,\ldots, n\}$.

I'm pretty sure Sipser's book has this example.

$\endgroup$
  • $\begingroup$ The construction in Siper's book produces a DFA with exactly 2^n states. If the NFA has the state set Q, then the state set of the DFA is Pow(Q) in order to simulate all the possible 'parallel' states an NFA migth be in. (edit to add opinion on question scope) Given that the construction used for this in a standard text clearly shows the possibility of an exponential number states, it seems to me that this isn't research level. Might be suitable as a reference request though. $\endgroup$ – Logan Mayfield Sep 16 '12 at 17:45
8
$\begingroup$

Another example is the language of all words which miss one symbol of the alphabet. If the alphabet is of size $n$, then a NFA can "guess" a starting state and so accept the language with $n$ states. On the other hand, using Nerode's theorem it is easy to see that the size of the minimal DFA for this language is $2^n$.

This example also shows that NFAs might incur an exponential blowup under complementation. Indeed, it is known that any NFA (or even context-free grammar) for the language of all words containing all symbols of the alphabet must have an exponential number of states.

$\endgroup$
  • 1
    $\begingroup$ In case anyone besides me initially misinterpreted it, "words which miss one symbol of the alphabet" means $\bigcup_{\sigma \in \Sigma} (\Sigma \setminus \sigma)^*$. (Not: words that contain every letter except one, or words that list the letters in order and skip one.) $\endgroup$ – 6005 Jun 30 '18 at 18:12
  • $\begingroup$ It's a bit of an odd example because the size of $\Sigma$ is not held constant for the family of examples. If we assume a fixed binary alphabet, we can adapt the example by encoding the $n$ letters in binary, but the result is a bit different. Assuming I didn't make a mistake, in that case we can get an NFA of size $O(n^2)$ and the DFA must be of size at least $2n \cdot 2^n$. $\endgroup$ – 6005 Jun 30 '18 at 18:20
  • $\begingroup$ The point of this example is that the blowup matches exactly the power set construction. There does exist a binary example with the same blowup, but it's more complicated. $\endgroup$ – Yuval Filmus Jun 30 '18 at 18:22
  • $\begingroup$ Yep, it's a nice example. $\endgroup$ – 6005 Jun 30 '18 at 18:22
  • 1
    $\begingroup$ By the way, your binary example can be improved to $O(n\log n)$ by using binary rather than unary encoding. $\endgroup$ – Yuval Filmus Jun 30 '18 at 18:25

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.