Minimizing a graph – graphically!

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, s_0 and s_1 output 0‘s on both inputs, but s_3 outputs on input 1. It turns out, s_3 is the only one that differs. So what we can conclude is that {s_0,s_1,s_2,s_4} behave the same. s_3 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 s_2 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 s_2. Think about this for while, it is the core idea. We can therefore distinguish s_2 from  {s_0,s_1,s_4}. 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 s_1 and s_4. On input 1, they both go to s_2 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 s_1 from s_4, 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 s_0. Otherwise we are in {s_3,s_2,s_1}. We note that we can never have a perfect strategy if the graph had s_4 in it, since it would always come down to the uncertainty of the marker being in s_1 or s_4.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s