# Finding if two machines can be equivalent

I have this problem:

Consider the following machines M1 and M2.
M1 has initial state A and the initial state of M2 is unspecified.
Can the machines be made equivalent by the correct choice of initial state for M2? If so, which state(s) can be chosen?

I'm not sure how to show it? I broke the two machines to partitions, but I don't know if this is the right step to do. I have the tables of states of the FSMs, but I don't think you need it to help me.

The tables are:

Thanks

-
Assuming that I couldn’t tell by eye, I’d reduce the machines to minimal equivalent FSMs $\mathbf{M_1}$ and $\mathbf{M_2}$ and see if the two were identical apart from the missing initial state in $\mathbf{M_2}$. – Brian M. Scott Oct 5 '12 at 3:25
@BrianM.Scott reduce means partition the machine right? for example: M1: {A}{H}{B,G}{C,D}{E}{F} and M2: {A}{E,L}{J,M}{B,N}{G}{C}{E}{H}{D,K} these are the equivalent states in each machine. So M1 and M2 can't be equivalent since M2 has more states? I will add the tables – Mike Oct 5 '12 at 3:34
No, Mike, there's a whole reduction procedure that's probably in some text or notes you're using. – Gerry Myerson Oct 5 '12 at 4:41
The numbers of states are deceptive, because one of the reduced DSMs has two disconnected components; see my answer. – Brian M. Scott Oct 5 '12 at 4:41

If you look closely at the minimal DSM $\mathbf{M_2}'$ that you get from $\mathbf{M_2}$, you’ll see that it has two disconnected components, one consisting of the states $\{A\},\{F\}$, and $\{H\}$ and the other of the states $\{E,L\},\{J,M\},\{B,N\},\{D,K\},\{G\}$, and $\{C\}$; let $\mathbf{M_2}''$ be the DSM consisting only of the second component, the one with six states. The minimal DSM $\mathbf{M_1}'$ that you get from $\mathbf{M_1}$ also has six states, $\{E\},\{F\},\{A\},\{B,G\},\{H\}$, and $\{C,D\}$. If you actually sketch the graphs of these DSMs, you’ll notice that they have a lot in common: two loops, and a pair of vertices with transitions going both ways between them. A little more work reveals that they are in fact isomorphic, with the states matching up according to the following table:
$$\begin{array}{c} \mathbf{M_1}'&\mathbf{M_2}''\\ \hline \{A\}&\{B,N\}\\ \{E\}&\{E,L\}\\ \{F\}&\{J,M\}\\ \{B,G\}&\{D,K\}\\ \{C,D\}&\{C\}\\ \{H\}&\{G\} \end{array}$$
Thus, $\mathbf{M_1}$ and $\mathbf{M_2}$ are actually equivalent.