1. Home
2. Academy
3. State Machines from Zero
4. Volume 10

10.1 Why fewer states matter

Machines designed from a story often contain states that do exactly the same job. Merging them gives a smaller machine that behaves identically.

Where extra states come from

When you design from a word problem, it is natural to make a new state for every situation the story mentions. But two situations that sound different may lead to exactly the same future: the same outputs now, and the same behaviour for every input that follows. Such states are duplicates. Finding them and merging them is called state minimisation.

Here is a machine with seven states, one input x and one Moore output z. It was written without any thought for size:

No two rows are identical, so there is no obvious duplicate. Yet, as you will see in sub-module 10.3, this machine behaves exactly like a machine with only four states.

Why a smaller machine is better

• Fewer flip-flops - sometimes. With binary codes, 7 states need 3 flip-flops and 4 states need 2. The saving appears only when the count drops below a power of two: 6 states still need 3.
• Less logic. Fewer states means fewer rows in the table, and usually smaller next-state and output logic.
• Less to test. Every state times every input is a case to check. Fewer states, fewer cases.
• Easier to understand. A duplicate state is a trap for the next person to read the design.

Unreachable states

A simpler kind of waste is an unreachable state: one that no sequence of inputs can ever reach from the reset state. Find them by starting at the reset state and following every arrow; any state you never visit can be deleted at once. Always do this first - the methods in this volume assume every state can be reached.

10.2 Equivalent states

Two states are equivalent if no sequence of inputs can tell them apart: from either one, every input sequence gives exactly the same outputs.

Telling states apart

Imagine the machine in a sealed box. You can press its input buttons and watch its outputs, but you cannot see which state it is in. Two states are equivalent if, whatever you press, you can never tell which of the two it started in.

The two tests

To be equivalent, two states must pass both tests:

1. Same outputs now. In a Moore machine, the same output. In a Mealy machine, the same output for every input.
2. Equivalent next states. For every input, the two next states must themselves be equivalent - or be the same state.

The second test refers back to equivalence itself. That is why we need a method: we cannot just look at two rows and decide. The methods in the next two sub-modules solve this circle step by step.

A sequence that tells them apart

To prove two states are not equivalent, one input sequence is enough - a sequence that makes them give different outputs. It is called a distinguishing sequence.

In the seven-state machine, take states A and B. Both have z = 0, and on x = 0 both go to E. Only x = 1 differs: A goes to D, and B goes to G. Now feed each the sequence 1, then 0:

The third output differs, so A and B are not equivalent. Each takes one input to show that its next states differ, and one more to show it in an output.

10.3 The partition method

The partition method starts with the states grouped by their outputs, then keeps splitting any group whose members lead to different groups, until nothing splits.

A partition is a split of the states into groups, where every state is in exactly one group. The method builds better and better partitions, called P0, P1, P2 and so on.

1. P0: group by output. States with different outputs can never be equivalent, so they start in different groups.
2. Refine. In each group, look at where every state goes on each input - not the state's name, only which group it lands in. States that land in the same groups stay together; the others split off.
3. Repeat the refine step on the new partition.
4. Stop when a refine step changes nothing. Each group is one state of the minimal machine.

Worked example

Apply it to the seven-state machine from sub-module 10.1.

P0 - group by z. The states with z = 0 are A, B, D, E and G. The states with z = 1 are C and F.

P0 = { A B D E G } { C F }

P1 - refine. For each state in the big group, write the group it lands in for x = 0 and x = 1. Call the groups "zero" and "one" after their output:

D and E have a different pattern from A, B and G, so they split off. In the group { C F }, C goes to (C, B) and F goes to (C, G) - the same groups, so they stay together.

P1 = { A B G } { D E } { C F }

P2 - refine again, with the new groups:

A now lands in a different group on x = 1, so A splits off. The groups { D E } and { C F } still agree inside themselves.

P2 = { A } { B G } { D E } { C F }

P3 - refine once more. B and G both go to { D E } on 0 and { B G } on 1. D and E both go to { C F } on 0 and { D E } on 1. C and F both go to { C F } on 0 and { B G } on 1. Nothing splits, so P3 = P2, and we stop.

The minimal machine

Each group of P2 becomes one state. Name each after its members:

To draw it, take any member of each group and follow its arrows. For example, B goes to E on 0 and to G on 1, so the merged state BG goes to DE on 0 and to BG on 1. Any member gives the same answer - that is exactly what the partition guarantees.

10.4 The implication table

The implication table checks every pair of states at once. Cross out the pairs with different outputs, write down what each remaining pair depends on, then keep crossing out until nothing changes.

The implication table is the other classic method. It works especially well by hand for Mealy machines, and it answers a slightly different question: not "what are the groups?" but "which pairs are equivalent?".

The example

A Mealy machine with six states, one input x, and one output. Each entry reads next state / output:

The method

1. Draw the table. One cell for every pair of states, in a staircase: rows B to F, columns A to E.
2. Pass 0. Cross out (X) every pair whose outputs differ for some input.
3. Fill in. In every other cell, write the pairs of next states that must also be equivalent - one pair per input. Leave out a pair of two identical states, and leave out the cell's own pair.
4. Repeat passes. Cross out every cell that lists a pair already crossed out. Keep making passes until one pass crosses out nothing.
5. Read off. Every cell left uncrossed is an equivalent pair.

Pass 0 and filling in

Only C has a different output (0 on x = 0), so every pair containing C is crossed out at once. The other cells list what they depend on. For example, A and B go to B and C on x = 0, and to A and D on x = 1. So the cell A-B lists "A-D, B-C":

The passes

• Pass 1. A-B lists B-C, which is crossed. B-D and B-E list C-E, crossed. B-F lists C-F, crossed. Cross out all four.
• Pass 2. A-D lists B-E, crossed in pass 1. A-E lists B-E too, and A-F lists B-F. Cross out all three.
• Pass 3. The only cells left are D-E, D-F and E-F. Each lists only pairs among D, E and F - none crossed. Nothing changes, so we stop.

The result

D, E and F are all equivalent to each other, so they merge into one state. A, B and C stay alone. Six states become four:

Notice what the three merged states had in common: from any of them, the machine never again reaches C, so the output can never be 0 again. The table found that without anyone having to spot it.

Which method to use?

Both always give the same minimal machine.

10.5 GATE-style minimisation problems

Exam problems on minimisation test the same two ideas every time: group by output, then split by where the states go. A few patterns come up again and again.

These are practice problems in the style of written exams such as GATE, written for this course. Try each one before you open the solution.

What you learned

• Equivalent states cannot be told apart by any input sequence; merging them never changes what the machine does.
• Remove unreachable states first, then look for equivalent ones.
• One distinguishing sequence is enough to prove two states differ.
• The partition method: group by output, then keep splitting groups whose members lead to different groups, until nothing splits.
• The implication table: cross out pairs with different outputs, list what each pair depends on, and keep crossing out, pass after pass.
• A smaller machine saves flip-flops only when it drops below a power of two, but it always simplifies testing.

Key words from this volume

Every word below has a plain-English entry in the glossary.

• State minimisation
• Unreachable state
• Equivalent states
• Distinguishing sequence
• Partition
• Implication table
• Incompletely specified machine

Interview corner

Next, Volume 11 asks what happens when a machine lands in a state it should never be in - and how to make sure it always finds its way home.