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



1 Answer 1


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

  • $\begingroup$ I'm not sure I can show that. Are we assuming p is equivalent to q? $\endgroup$
    – Mike
    Oct 27, 2012 at 13:53
  • $\begingroup$ 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). $\endgroup$ Oct 27, 2012 at 17:59
  • $\begingroup$ 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? $\endgroup$
    – Mike
    Oct 27, 2012 at 22:43
  • $\begingroup$ Any Help? can you please respond to my comments? $\endgroup$
    – Mike
    Nov 1, 2012 at 4:15
  • $\begingroup$ @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. $\endgroup$ Nov 1, 2012 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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