Upper-bounds intersection NFA

Question

Say nX and nY is the number of states in a DFA X and Y, defined by the regular languages A and B respectively. What would be the upper-bounds for an NFA which recognizes AꓵB?

Answer 1

The product construction tells us that, given a DFA $M_1$ with $|Q_1|=k_1$ and a DFA $M_2$ with $|Q_2| = k_2$, we can build a DFA $M_{12}$ such that $L(M_{12}) = L(M_1) \cap L(M_2)$ with at most $k_1k_2$ reachable states. This is the case, since the product construction tells us that $Q_{12} = Q_1 \times Q_2$.