# Reducing states in a finite-state machine using compatibility classes, for an incompletely specified machine

In the process of reducing the states of a synchronous finite state machine first we need to create maximal compatibility classes (of states; which states can be compatible, i.e. the "don't cares" can be set such as the states become compatible). After creating maximal compatibility classes we have to create minimal compatibility classes, starting from the maximal classes (pick just some classes, so that every state appears in at least one).

The conditions that these minimal compatibility classes have to satisfy are:

1. Closure (for the same input, all the states from a class have to be followed by states belonging to a same class)

2. If two states are in the same class and this is a condition for other two states to be compatible, the other two states have to be in the same class.

I would like to know why is the second condition necessary.

The second condition says that if states $s_i$ and $s_j$ are compatible if states $s_m$ and $s_n$ are compatible, then if $s_m$ and $s_n$ are in the same class, then $s_i$ and $s_j$ must be in the same class too. I thought of a reason and I would like to know if I am right. I will use a notation: $s_i$ compatible with $s_j$ <=> $s_i$ ~ $s_j$. So if $s_i$ ~ $s_j$ if $s_m$ ~ $s_n$ and $s_m$ and $s_n$ are in the same class and $s_i$ and $s_j$ are in different classes means that I chose the "don't cares" in such a way that $s_i$ and $s_j$ are not compatible and that means that $s_m$ and $s_n$ are not compatible anymore (they can't belong to the same class).

• Good, this is a nice improvement! Thank you. Let me share some more feedback. (1) My suggestion would be to try some examples, comparing what you get with the second condition vs what you get without it. (2) Minor nitpick: Your first sentence say that to reduce the number of states in a finite state machine, we need to first create maximal compatibility classes of states. This does not sound right to me: there are many ways to reduce the states of a finite state machine. Similarly for the "we have to" statement in the second sentence. – D.W. May 12 '14 at 19:50
• This is the only method I've learnt. Is my explanation correct? – user42768 May 12 '14 at 19:54
• I am sorry for my impatience, but is my explanation correct? – user42768 May 13 '14 at 14:58