# Implication chart method for state reduction

I'm not understanding implication charts to reduce states for Mealy and Moore machines. I'm looking at an example from berkley

I was able to construct the table and then also eliminate the ones based on that output(here's the one from the site since you can't see my whiteboard) The thing is, I don't understand how they got to the next step. How did they decide to eliminate those states? Following the steps, I wound up eliminating several steps they kept, such as a and d, since c and e are clearly not the same.

What am I missing?

• The rules were given, but hard to explain/expand one by one... eecs.berkeley.edu/~newton/Classes/CS150sp98/lectures/week8_1/…
– user41337
May 6, 2014 at 2:24
• I did read the rules. I can deconstruct a lot of these based on the table, unfortunately I think I'm going to need to know the implication method.
– JFA
May 6, 2014 at 3:45

Let's first look at the a-b box (the topmost one). In the box it says d-f, c-h. First you look at the d-f box, there is a cross. This means that d-f is invalid. Thus any box that contains d-f, in this case it will be the a-b box which we are concerned right now, should be crossed out. Repeat it again to other "alive box"s.

We need to check each unchecked box. For instance, a == d (only if c == e) and vice versa. This check is the only true condition as per the state table possible for reduction.

For any other case, the condition is not valid. For instance, if you were to check the crossection between c and f, you will notice the following conditions:

1. e == f and b == d

check the intersection of e and f, we find: e == f and a == b.

Now check a and b intersection, we find: a == b and c == h

It is only now that we notice that c is not equal to h. Therefore, any conditions related to this category it also not true.

So, since c != h, we can say the following: a !=b, and e !=f.

It is tedious, but yeah this is the way to go. In simple terms, the goal is to find one untrue condition and all things related to it. The remaining terms, if any, should by used for reduction.

Good luck!