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

Suppose $M_1 = \langle Q_1,S,R,f_1,g_1\rangle$ and $M_2 = \langle Q_2,S,R,f_2,g_2\rangle$ are two strongly connected machines.

I need to show that $M_1 \equiv M_2$ iff there exist a state $p \in Q_1$ and a state $q \in Q_2$ such that $p \equiv q$.


share|cite|improve this question

I assume this is homework, so I'll just give a hint. If it's not enough, please let me know where you're getting stuck and I'll try to help.

A finite state machine being strongly connected means that any state can be reached from any other through some sequence of transitions. In particular, this means that any state in $Q_1$ can be reached from $p$ for some input, and similarly for $Q_2$ and $q$.

For any state $x \in Q_1$, let $A$ be an input that takes $M_1$ from $p$ to $x$. Let $y \in Q_2$ be the state obtained by starting $M_2$ in state $q$ and feeding it the input $A$. Can you show that $x \equiv y$?

Edit: While trying to write a more detailed answer, I realized that, under (what I would consider) the usual definitions of FSM equivalence and strong connectedness, the result to be proven does not actually hold.

Definition 1 (equivalence of finite state machines): Two finite state machines $M_1$ and $M_2$ are equivalent ($M_1 \equiv M_2$) if they have the same input and output alphabets and if, starting from their respective initial states, they produce the same output for any input string.

Definition 2 (equivalence of states): Two states $p$ (of finite state machine $M_1$) and $q$ (of machine $M_2$, which may or may not be the same as $M_1$) are equivalent ($p \equiv q$) if the machines they belong to have the same input and output alphabets and if, for any input string, machine $M_1$ started from state $p$ produces the same output as machine $M_2$ started from state $q$.

Definition 3 (strongly connected machines): A finite state machine $M$ is strongly connected if, for any states $s$ and $r$ in the state space of $M$, there exists a finite sequence of transitions that takes $M$ from state $s$ to state $r$.

For a counterexample, consider a machine $M$ with two states, $\rm x$ and $\rm y$, such that for any valid input symbol, $M$ in state $\rm x$ moves to state $\rm y$ and outputs $\rm a$, and $M$ in state $\rm y$ moves to state $\rm x$ and outputs $\rm b$. Let $M_1$ be $M$ with initial state $\rm x$, and let $M_2$ be $M$ with initial state $\rm y$.

Clearly, for any input, $M_1$ outputs $\rm ababab\dots$ while $M_2$ outputs $\rm bababa\dots$, so $M_1 \not\equiv M_2$. Yet $M_1$ and $M_2$ only differ in their initial states, so, in particular, the state $\rm x$ of $M_1$ is equivalent to the corresponding state $\rm x$ of $M_2$.

share|cite|improve this answer
I'm not sure I can show that. Are we assuming p is equivalent to q? – Mike Oct 27 '12 at 13:53
Um, yes. I assumed the part you have difficulty in is showing that $p \equiv q \implies M_1 \equiv M_2$ (since, obviously, if $M_1 \equiv M_2$ then their initial states are equivalent). – Ilmari Karonen Oct 27 '12 at 17:59
you right. ahh, I see. So if p equivalent to q, and A takes from p to x and from q to y, it means x is equivalent to y. when we say two states are equivalent, we mean that their outputs and their next states are equivalent,right? But i'm not sure how it helps me to prove my problem. Can you explain a little bit more? – Mike Oct 27 '12 at 22:43
Any Help? can you please respond to my comments? – Mike Nov 1 '12 at 4:15
@Mike: See the edit to my answer above. On closer inspection, it looks to me like the result you're asked to prove is not actually true. – Ilmari Karonen Nov 1 '12 at 16:05

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.