The aim of this post is to illustrate how to minimize (any graph stemming from a determinstic finite state machine). I will do so by giving a simple example:

Let’s start off with a simple graph, as the one above. Let the symbols on the edges be i/o, i.e. we jump to next state via the edge corresponding to our input i and at the same time, we output o. In this case, the symbols are 0 and 1, but they can be any symbols; banana, apple and pear, as long as they are distinguishable in any sense.

We can think of the minimization as a guessing-game between two players. Player A places its marker on a state. Now player B should tell which state the marker is at. Ok, assume that we take the role as player B. The first thing we can do is to distinguish the states that output differently on the inputs.

For instance, and  output 0‘s on both inputs, but  outputs 1 on input 1. It turns out,  is the only one that differs. So what we can conclude is that  behave the same.  behaves in its own way. So what happens? We get two groups:

Now, we cannot distinguish between direct responses – we already did that and it won’t make a difference from now on. What we can do, however, is to determine if a state jumps to a state which already is distinguishable. Since jumps, on input 0, to a state that we can distinguish from the other, while the other states in the circle doesn’t, we know that sending a sequence 01 will give us output 1, if and only if we start in . Think about this for while, it is the core idea. We can therefore distinguish  from  . So we get the graph:

Do the next step yourself. If you do it right, you will get:

Alright, so let’s try to distinguish the last states and . On input 1, they both go to and on input 0, they stay in a set of states which are assumed to be mutually indistinguishable. Therefore, they behave the same. Since, we made no changes to the circles and we will do the very same things in the next step, the circles will remain constant. Therefore, we can never distinguish  from , and therefore the can be regarded as one. We get the minimized graph:

So, this algorithm is called the RF-algorithm. What I am proposing is a graphical interpretation of it, which I believe is more efficient in a pedagogical sense.

To conclude (not important for the minimization problem, but for the guessing-game), we can see that we have a strategy for determining what state we are in. Assume that we clone the instance 3 times and for each we send in one of the sequences {1,01,101}. If none gives output 1, we are in . Otherwise we are in . We note that we can never have a perfect strategy if the graph had in it, since it would always come down to the uncertainty of the marker being in  or .