# State complexity of difference of two languages

Given $$A_1$$ - DFA with $$n$$ states, $$A_2$$ - NFA with $$m$$ states (both over the same alphabet - $$\Sigma$$). What's the state complexity, i.e. an upper bound for the amount of states of the minimal DFA, recognizing the language $$L(A_1)\setminus L(A_2)=L(A_1) \cap(\Sigma^*\setminus L(A_2))$$.

What I thought of: evaluate the state complexity of $$\Sigma^*\setminus L(A_2)$$ (hypothesis: $$2^m$$). Why? Because an upper bound of $$2^m$$ can be obtained for a DFA to accept the language of $$A_2$$. It's also known that the state complexity of the completion $$\Sigma^*\setminus L(A_{min})$$ is $$k$$, where $$A_{min}$$ is an arbitrary minimal $$DFA$$ with $$k$$ states. Therefore we can evaluate the upper bound of the minimal DFA, recognizing $$L(A_1) \cap(\Sigma^*\setminus L(A_2))$$ as $$n2^m$$ (the state complexity of the intersection is simply the product of states).

This is correct, and moreover it is tight for $$n = 1$$, even for a binary alphabet (but not for a unary alphabet!). Indeed, it is well-known that there are language accepted by $$m$$-state NFAs which require $$2^m$$ states for a DFA. Since the DFA complexity of a language and its complement coincide, taking $$A_1 = \Sigma^*$$ we obtain a tight example with $$n = 1$$ and any $$m$$.

It is an interesting question whether the bound is tight for all $$n$$. This is likely the case if we take for $$L(A_1)$$ the language $$(\Sigma^n)^*$$.