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?

  • $\begingroup$ I don't see the relevance of the pumping lemma here. $\endgroup$ – Yuval Filmus Mar 20 '18 at 6:51
  • 1
    $\begingroup$ A good start is constructing the product automaton. $\endgroup$ – Yuval Filmus Mar 20 '18 at 6:52
  • $\begingroup$ Using cross product method? $\endgroup$ – nicole Mar 20 '18 at 6:52
  • $\begingroup$ Probably. I've never heard this term before in the context of finite automata. $\endgroup$ – Yuval Filmus Mar 20 '18 at 6:53
  • $\begingroup$ Sorry, the Cartesian Product method? Isn't that used for the intersection? stackoverflow.com/questions/7780521/… $\endgroup$ – nicole Mar 20 '18 at 6:54

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.

| cite | improve this answer | |

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.