Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

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:


share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer
So I was in the right direction? I just didn't see that there are two disconnected components. Thanks Brian. – Mike Oct 5 '12 at 11:24
@Mike: You’re welcome. As long as the machines are fairly small, I recommend sketching the graphs: most people get a better overall picture of what the machine does from the graph than from the table. In this case that would have made the disconnected components really obvious. – Brian M. Scott Oct 5 '12 at 11:26
In my book the definition of reduced is "a FSM is reduced if it contains no pair of equivalent states" and we are doing it by partitioning the state set no? – Mike Oct 5 '12 at 11:34
@Mike: That’s the most common way to do it, yes. (There is another algorithm that works beautifully, but it’s very far from obvious why it works.) – Brian M. Scott Oct 5 '12 at 11:36
I understand. Thanks – Mike Oct 5 '12 at 11:37

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.