# Show Two f.s.a. machines accept different input

I'm trying to solve it for two hours already. I know it somehow related to the pumping lemma

Let $M_1 = \langle Q_1,S,f_1,s_1,F_1\rangle$ and $M_2 = \langle Q_2,S,f_2,s_2,F_2\rangle$ be two machines, where $|Q_1|=m$ and $|Q_2|=n$.
Then $T(M_1) \not= T(M_2)$ iff there exists $x$ where $|x| < m*n$ such that $x$ is accepted only by one of the machines.

Thanks

-

Suppose that $T(M_1)\ne T(M_2)$. Then there is a shortest word $w$ that is accepted by one but not the other. If $|w|<mn$, we’re done, so suppose that $|w|\ge mn$.

Define a sequence of pairs $\langle q_k^1,q_k^2\rangle\in Q_1\times Q_2$ as follows. First, $q_0^1=s_1$ and $q_0^2=s_2$. Given $\langle q_k^1,q_k^2\rangle$ for some $k\le|w|$, let $\sigma_k$ be the $k$-th symbol in $w$, and let $$\langle q_{k+1}^1,q_{k+1}^2\rangle=\big\langle f_1(q_k^1,\sigma_k),f_2(q_k^2,\sigma_k)\big\rangle\;.$$

The sequence $\big\langle\langle q_k^1,q_k^2\rangle:k=0,\dots,|w|\big\rangle$ traces out the sequences of states through which the input $w$ sends both $M_1$ and $M_2$: the first coordinate follows the states in $M_1$, the second in $M_2$.

Since $|w|\ge mn$, there must be indices $i$ and $k$ such that $0\le i<k\le|w|$ and $\langle q_i^1,q_i^2\rangle=\langle q_k^1,q_k^2\rangle$. Let $w'$ be the word obtained from $w$ by deleting the segment $\sigma_{i+1}\sigma_{i+2}\dots\sigma_k$. You can easily verify that $f_1^*(s_1,w')=f_1^*(s_1,w)$ and $f_2^*(s_2,w')=f_2^*(s_2,w)$, so $w'$ is also accepted by exactly one of the automata $M_1$ and $M_2$, contradicting the assumed minimality of $|w|$.

-
@brian-m-scott Why do you see that if $|w| < mn$ we are done? – Mike Nov 1 '12 at 22:03
@Mike: Because the problem is to prove that if $T(M_1)\ne T(M_2$), then there is a word of length less than $mn$ that is accepted by one of the automata but not the other. If $|w|<mn$, it is such a word, and there’s nothing more to prove. – Brian M. Scott Nov 1 '12 at 23:28
@brain-m-scott Thank you very much. you are a great helper. – Mike Nov 2 '12 at 1:08
@Mike: You’re welcome, and thank you. – Brian M. Scott Nov 2 '12 at 1:09