Length of shortest word accepted by exactly one of two DFAs

Question

Let $M_1$ and $M_2$ be two deterministic finite automata with $M_1$ having $n$ states, and $M_2$ having $m$ states, over the same alphabet $\Sigma$. Show that if $M_1$ and $M_2$ are not equivalent, then there is some string $\omega \in \Sigma^*$ of length at most $n \times m$ that is in exclusively $M_1$ or $M_2$.

It is clear to me that since they are not equivalent, there is some string that is in exclusively $M_1$ or $M_2$. But how can we show that there is some string that does not exceed the required length?

Answer 1

Construct the product automaton $M = M_1 \times M_2$, which contains $nm$ states. Since $L(M_1) \neq L(M_2)$, the automaton $M$ contains a state $(q_1,q_2)$ reachable from its initial state such that $q_1$ is an accepting state of $M_1$ and $q_2$ is not an accepting state of $M_2$, or vice versa. Since $M$ contains $nm$ states, this state is reachable from the initial state of $M$ by a path of length at most $nm-1$. This corresponds to a word of length $nm-1$ which is in $L(M_1)$ but not in $L(M_2)$, or vice versa.

Using the method of this answer, we can improve the bound to $n+m-2$. This is tight for $m=1$, as the example of $L(M_1) = \sum_{k=0}^{n-2} \Sigma^k$ and $L(M_2) = \Sigma^*$ shows.