15
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.

$\endgroup$

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.