Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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$.
Thanks
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$.
