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|, 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 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|$.

  • 0
    @Mike: You’re welcome, and thank *you*.2012-11-02