State Reduction of SSCs

1. Partition states by their outputs
2. For each partition, iteratively do the following:
   For any input pattern, if different states in the partition transition to another partition, then those states are not equivalent and we separate them into smaller partitions
3. Keep partitioning until all the states in each partition transition to the same other partition for any input pattern

Consider the following state table:

First, we group by output. States ABD output 1, and CEFG output 0.

Next, we partition ABD's next states:

• When , BDB
• When , CFG

Observe that BDB all belong in ABD, and CFG all belong to CEFG. This means these states may be equivalent.

We repeat this for :

• When , FFEF
• When , ECDG

Observe that while FFEF all belong to CEFG, in ECDG, D belongs to a different partition (ABD), while ECG belong to the CEFG partition. Thus, while state 0, 1, and 3 may be equivalent, state 2 cannot (since D is the second element of ECDG), which means in CEFG, CEG may be equivalent, and F is not.

We have to keep doing this until all no more partitions should be made. This will get messy, so we will instead structure this in a tree:

Thus, we see that:

Now, we remove any redundant states, and then replace the removed states with their equivalents. That is, we remove present state rows D, E, and G, and replace any occurrences of D with A, and any occurrences of E and G with C.

Finally: