Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
up vote 1 down vote accepted

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

share|cite|improve this answer
@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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.