# Exponential separation between NFAs and DFAs in the presence of unions

For a regular language $$L$$, its DFA complexity is the size of the minimal DFA accepting it, and its NFA complexity is the size of the minimal NFA accepting it. It is well-known that there is an exponential separation between the two complexities, at least when the size of the alphabet is unbounded. Indeed, consider the language $$L_n$$ over the alphabet $$\{1,\ldots,n\}$$ consisting of all words not containing all symbols. Using the Myhill-Nerode theorem it is easy to calculate the DFA complexity $$2^n$$. On the other hand, the NFA complexity is only $$n$$ (if multiple initial states are allowed; otherwise it is $$n+1$$).

Problem 1.65 of Sipser's Theory of Computation concerns the DFA covering complexity of a language, which is the minimal $$C$$ such that $$L$$ can be written as the (not necessarily disjoint) union of languages of DFA complexity at most $$C$$. The DFA covering complexity of $$L_n$$ is only $$2$$.

Is there an exponential separation between NFA complexity and DFA covering complexity?

• Advanced variant: here we're combining DFAs (or rather, the languages they accept) through union. What if we allow an arbitrary "circuit" (union, intersection, perhaps complement)? Does that help? Jul 12, 2020 at 15:31
• Where do 'regular expressions' (defined by the closure of any character, concatenation, union, and Kleene star) fall in this separation? There is a (roughly) size-preserving mapping from regular expression to NFA, but the converse is not true. Yet there is an exponential separation between regular expressions and DFAs as well (consider the DFA for $(0\mid 1)^*1(0\mid 1)^k$).
– orlp
Jul 12, 2020 at 15:35
• @orlp There is an exponential separation. See Theorem 24 here. Jul 12, 2020 at 15:40
• So in the 'polynomially sized recognizer hierarchy' we find that both DFAs and regular expressions are strictly less powerful than NFAs, but that DFAs and regular expressions are incomparable (having cases with exponential blowup both ways)?
– orlp
Jul 12, 2020 at 15:51
• Yes, I believe that's true. Jul 12, 2020 at 15:55

Consider the language $$M_n = (L_n \#)^*L_n$$, where $$\#$$ is a new symbol.

The NFA complexity of $$M_n$$ is $$n$$ (allowing for multiple initial states). Indeed, here is one NFA having $$n$$ states accepting $$M_n$$. The states are $$q_1,\ldots,q_n$$, all both initial and final. There is a self-loop around $$q_i$$ for each $$j \neq i$$. Furthermore, there are transitions from each $$q_i$$ to each $$q_j$$ labeled $$\#$$. The matching lower bound follows from the DFA complexity of $$L_n = M_n \cap \{1,\ldots,n\}^*$$ being $$2^n$$.

In contrast, we will show that the DFA covering complexity of $$M_n$$ is $$2^n$$. For the upper bound, consider a DFA whose states are $$q_S$$ for $$S \subseteq \{1,\ldots,n\}$$. The states keep track of the letters seen so far: the initial state is $$q_\emptyset$$, and $$\delta(q_S,i) = q_{S \cup \{i\}}$$. All states other than $$q_{\{1,\ldots,n\}}$$ are accepting. When seeing $$\#$$, if we're in $$q_{\{1,\ldots,n\}}$$ then we stay put, and otherwise we move to $$q_\emptyset$$.

Let $$[n] = \{1,\ldots,n\}$$. For $$S \subseteq [n]$$, let $$w_S$$ consist of all letters in $$S$$ in order. Let $$P$$ denote all words over $$[n]$$ containing each letter at most twice, and missing at least one letter.

Suppose that $$M_n = \bigcup_{i=1}^N L(A_i)$$, where the $$A_i$$ are DFAs. We can identify $$L_i := L(A_i) \cap (P\#)^*P$$ with a language over the alphabet $$P$$ in the natural way ($$p_1\#\ldots\#p_\ell$$ corresponds to the word of length $$\ell$$ whose letters are $$p_1,\ldots,p_\ell$$). Say that $$x \in P^*$$ is good for $$L_i$$ if for all $$p \in P$$ there exists $$y_p \in P^*$$ such that $$xpy_p \in L_i$$.

Suppose that no $$x$$ is good for $$L_i$$. Let $$\ell \geq 0$$. For $$0 \leq r \leq \ell$$, let $$S_r$$ be the set of length $$r$$ prefixes of words in $$L_i \cap P^\ell$$. If $$|S_{r+1}| > (|P|-1)|S_r|$$ for some $$r < \ell$$, then by the pigeonhole principle there is some $$x \in S_r$$ such that $$xp \in S_{r+1}$$ for all $$p \in P$$; but then $$x$$ is good. It follows that $$|L_i \cap P^\ell| = |S_\ell| \leq (|P|-1)^\ell |S_0| = (|P|-1)^\ell$$.

If no $$x$$ is good for any $$A_i$$, then for all $$\ell \geq 0$$ we have $$|P|^\ell \leq \sum_{i=1}^N |L_i \cap P^\ell| \leq N(|P|-1)^\ell,$$ which is contradictory for large enough $$\ell$$. Therefore some $$x$$ is good for some $$A_i$$.

Let us identify $$x \in P^*$$ with the corresponding word over $$[n] \cup \{\#\}$$. Thus for each $$p \in P$$ there is $$y_p \in M_n$$ such that $$x\# p\# y_p \in L(A_i).$$

We claim that the $$2^n$$ words $$x \# w_S$$ (we allow $$S = [n]$$) are pairwise inequivalent in the Myhill–Nerode relation of $$L(A_i)$$, and so $$A_i$$ has at least $$2^n$$ states.

Indeed, let $$S,T$$ be two different subsets of $$[n]$$. Assume without loss of generality that $$j \in T \setminus S$$. Since $$w_S w_{[n] \setminus \{j\}} \in P$$, by assumption $$x \# w_S w_{[n] \setminus \{j\}} \# y_p \in L(A_i)$$, where $$p = w_S w_{[n] \setminus \{j\}}$$. In contrast, $$w_T w_{[n] \setminus \{j\}}$$ contains all letters, hence $$x \# w_T w_{[n] \setminus \{j\}} \# y_p \notin M_n$$, and so $$x \# w_T w_{[n] \setminus \{j\}} \# y_p \notin L(A_i)$$. This shows that the two words $$x \# w_S, x \# w_T$$ are inequivalent.