0
$\begingroup$

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:
http://imageshack.us/a/img507/604/26588241.png

Thanks

  • 0
    The numbers of states are deceptive, because one of the reduced DSMs has two disconnected components; see my answer.2012-10-05

1 Answers 1

0

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.

  • 0
    @Mike: Yes, that’s right.2012-10-06