State Equivalence and the Implication Table

State equivalence, formally

Two states $p$ and $q$ are equivalent, written $p \equiv q$, if starting from either one and feeding the machine any finite input bit sequence produces the same output bit sequence. Treating them as one state cannot be detected from the outside.

This is a recursive definition in disguise. For $p$ and $q$ to be equivalent the transitions out of both must agree, which means two things must hold for every input value $x$:

$\lambda(p, x) = \lambda(q, x) \qquad \text{and} \qquad \delta(p, x) \equiv \delta(q, x)$

where $\lambda$ is the output function and $\delta$ is the next-state function. In words: the outputs must match, and the next states must themselves be equivalent.

This is exactly the rule row matching applies, but with the extra freedom that the next states are allowed to be equivalent rather than literally identical. Row matching is the special case where “equivalent” is replaced by the much stricter “equal”.

The implication table

To use the rule above you need to test every pair of states $(p, q)$ for equivalence. The implication table is a triangular grid that lists one such pair in every cell. The rows are labelled with state names except the last, the columns are labelled with state names except the first, and the upper triangle (together with the diagonal) is omitted because those cells only duplicate information already present below the diagonal.

Each cell holds one of three things:

• An X, meaning the pair are definitely not equivalent. This happens whenever the outputs disagree (because the first half of the equivalence rule fails on the spot).
• A list of implied pairs, written D-F C-H, meaning ”$A \equiv B$ holds if $D \equiv F$ and $C \equiv H$”. When the outputs match, the next states are recorded as the conditions on which the answer depends.
• The cell is left empty once those implied pairs have been confirmed equivalent, in which case $p \equiv q$.

The procedure has three phases:

1. Fill the table. Compare every pair of states. Cross out any cell where the outputs differ. In every other cell write the implied next-state pairs, removing any “self-implied” pair such as A-D in the A-D cell (a state is always equivalent to itself, so it tells us nothing).
2. Sweep for non-equivalences. Walk the table. If a cell’s implied pair already appears as an X in the table, then the cell containing that pair must also be marked X. Each round of marking may unlock more Xs, so keep sweeping until no new Xs are added.
3. Read off the equivalences. The cells still containing (or now emptied of) implied pairs describe the equivalent state pairs. Merge them in the state table.

Worked example

Take this Mealy state table:

Current	Next $X{=}0$	Next $X{=}1$	Output $X{=}0$	Output $X{=}1$
A	D	C	0	0
B	F	H	0	0
C	E	D	1	1
D	A	E	0	0
E	C	A	1	1
F	F	B	1	1
G	B	H	0	0
H	C	G	1	1

There are 8 states, so the implication table has cells for every unordered pair: A-B, A-C, …, G-H.

Phase 1: fill in implied pairs

Compare A with every other state. The output row of A is 0, 0. States whose output is 1, 1 (C, E, F, H) cannot be equivalent to A, so cells A-C, A-E, A-F and A-H get an immediate X. For the states with output 0, 0 (B, D, G) we record the implied pairs from their next states:

• $A \equiv B$ if $D \equiv F$ and $C \equiv H$, so cell A-B contains D-F C-H.
• $A \equiv D$ if $C \equiv E$ (the self-implied $A \equiv A$ is dropped), so cell A-D contains C-E.
• $A \equiv G$ if $B \equiv D$ and $C \equiv H$, so cell A-G contains B-D C-H.

Continue column by column.

Phase 2: sweep for non-equivalences

Look at cell A-B, which holds implied pairs D-F and C-H. The D-F cell already contains an X, so D is not equivalent to F, so the condition for $A \equiv B$ is broken. Mark A-B with an X.

Now cell A-G has implied pair B-D. The B-D cell has just been marked X, so A-G fails too.

Continuing the sweep, cells B-D, B-G, C-F, D-G, E-F and F-H all get Xs (either because their implied pairs are already Xs, or because their implied pairs were Xed in the previous sweep). Sweep again, because those new Xs may knock out further cells. In this example the second sweep adds no fresh Xs, so the process terminates.

Phase 3: read off the equivalences

The only cells left unmarked are A-D and C-E, so:

$A \equiv D \qquad \text{and} \qquad C \equiv E$

Replace D with A and E with C throughout the state table, then delete rows D and E:

Current	Next $X{=}0$	Next $X{=}1$	Output $X{=}0$	Output $X{=}1$
A	A	C	0	0
B	F	H	0	0
C	C	A	1	1
F	F	B	1	1
G	B	H	0	0
H	C	G	1	1

Eight states have become six. Note that C now points to A on input 0 (where it used to point to E, but $E \equiv C$), and A points to A on input 0 (where it used to point to D, but $D \equiv A$). The outputs and external behaviour are unchanged.

Why the implication table always terminates

Each sweep only ever adds Xs to a finite table. Once a round passes with no new Xs, no future round can produce any either, so the algorithm must stop. This is a monotone process: cells move from “pending” to “marked X” and never back.

The unmarked cells that remain need a little thought. Some cells genuinely depend on no further pairs (they are empty or contain pairs that are all unmarked), and these describe real equivalences. The key invariant is that a cell with no X is a self-consistent set of implications: there is a smallest set of equivalent states that satisfies exactly those constraints, and merging them does not change the machine’s behaviour. This is enough to justify reading the answer off directly.

How this maps onto supervision questions

Most Tripos-style questions split into two parts:

• Row matching first, applied by inspection, removes states whose next states literally match. State this explicitly so the marker can see you have not skipped a step.
• State equivalence / implication table second, catches the remaining equivalences you cannot read off by eye.

If a question gives you a state table and asks for state reduction without specifying the method, do rows matching first and then run an implication table. The row-matching pass shrinks the table, so the implication table you draw afterwards is smaller and faster to complete.

See also:

• State Minimisation
• Row Matching