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

Recently an interesting question was asked and subsequently deleted.

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

The deleted question concerned 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?

Consider the language $M_n = \epsilon +(L_n \#)^*L_n$, where $\#$ is a new symbol. The NFA complexity of $M_n$ is $n$. We will show that its DFA covering complexity is $2^n$.
Let $A$ be a DFA accepting some language $L(A) \subseteq M_n$, with transition function $q_A$. Call a state $s$ viable if there is some word $w$ such that $q_A(s,w)$ is an accepting state. For any two non-failure states $s,t$, let $$A_{s,t} = \{ w \in (1+\cdots+n)^* : q_A(s,w) = t \}.$$ It is not hard to check that every word $w \in L(A)$ can be written as $w = w_1\# \cdots \#w_l$ where $w_i \in A_{s_i,t_i}$ for some viable $s_i,t_i$.
Suppose that $M_n = \bigcup_{i=1}^N L(A^i)$, where each $A^i$ is a DFA. Let $P$ be the lattice generated by all the languages $A^i_{s,t}$. We can view $L(A^i)$ as a language $L_P(A^i)$ over $P^*$, the space between any two symbols corresponding to $\#$. Under this viewpoint, $M_n$ corresponds to $P^*$.
Call $L_P(A^i)$ universal if for some $x \in P^*$ it is the case that for all $y \in P$ there is $z \in P^*$ such that $xyz \in L_P(A^i)$. We claim that some $L_P(A^i)$ is universal. Otherwise, each $L_P(A^i)$ contains at most $(|P|-1)^l$ words of length $l$. In total, the $L_P(A^i)$ must contain all $|P|^l$ words of length $l$, hence $|P|^l \leq N (|P|-1)^l$, which is violated for large enough $l$.
Suppose that $L_P(A^i)$ is universal, and write $A = A^i$ for brevity. Let $x' \in P^*$ be the corresponding prefix, and let $x \in M_n$ be some word corresponding to it. Thus for each $y \in L_n$ there is some $z_y \in M_n$ such that $x\#y\#z_y \in L(A_i)$.
For a subset $S \subseteq \{1,\ldots,n\}$, let $y_S$ consist of the letters in $S$ written in order. We claim that the words $x\#y_S$ are inequivalent for the Myhill-Nerode relation of $A$. Indeed, suppose $S \neq T$ and find some $a \in S \setminus T$ (without loss of generality). Then $x\#y_T y_{\{1,\ldots,n\} - a} \# z_{y_T y_{\{1,\ldots,n\} - a}} \in L(A)$ while $x\#y_S y_{\{1,\ldots,n\} - a} \# z_{y_T y_{\{1,\ldots,n\} - a}} \notin M_n$. Therefore $A$ must have a least $2^n$ states.