Finding the upper bound of states in Minimal Deterministic Finite Automata

Question

I have a task to determine the upper bound of states in the Minimal Deterministic Finite Automata that recognizes the language: $ L(A_1) \backslash L(A_2) $, where $ A_1 $ is a Deterministic Finite Automata (DFA) with $n$ states and $A_2$ is Non-deterministic Finite Automata (NFA) with $m$ states.

The way I am trying to solve the problem:

1. $ L(A_1) \setminus L(A_2) = L(A_1) \cap L(\Sigma^* \backslash L(A_2))$, which is language, that is recognised by an automaton $L'$ with $nm$ states.
2. Determinization of $L'$ which has $(nm)^2$ states and it is the upper bound of states.

Am I right?

Answer 1

This is wrong. Determinization of an NFA with $r$ states could result in a DFA with up to $2^r$ states. Therefore your argument actually gives an upper bound of $$2^{nm}. $$ This can be improved if you switch the order of operations. If you first convert your NFA to a DFA and only then apply the product construction, then you get the better bound $$ n2^m. $$

This bound is tight for infinitely many values of $n,m$. Consider the language $L_2$ of all words over $\Sigma^*\{\sigma_1,\ldots,\sigma_2\}$ that do not contain all letters. There is an NFA for $L_2$ (with multiple initial states) using only $m$ states. However, any NFA for $\overline{L_2}$ needs to contain at least $2^m$ states. Since $\overline{L_2} = \Sigma^* \setminus L_2$ and $\Sigma^*$ can be accepted by a single-state DFA, we see that the bound above is optimal.

You can probably show that the bound is tight for (practically) all $n,m$ by slightly modifying the above construction, replacing $\Sigma^*$ with $(\Sigma^n)^*$.