1
$\begingroup$

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

1 Answers 1

1

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|

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

  • 0
    @brian-m-scott Why do you see that if $|w| < mn$ we are done?2012-11-01
  • 0
    @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|2012-11-01
  • 0
    @brain-m-scott Thank you very much. you are a great helper.2012-11-02
  • 0
    @Mike: You’re welcome, and thank *you*.2012-11-02