[Solved]: Exponential separation between NFAs and DFAs in the presence of unions

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.