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
.