Row Matching

The rule

Two states $p$ and $q$ are row-match equivalent if, for every possible input value, they produce the same output and point to the same next state. In state-table terms: read off row $p$ and row $q$ and check character by character that every column agrees.

If row $q$ matches row $p$, then:

• replace every occurrence of $q$ in the next state columns with $p$, then
• delete row $q$ from the table.

This sometimes frees up further rows: now that $q$ has gone, another pair of rows may become identical. Repeat until no two rows match.

Worked example (Mealy)

Take this Mealy state table from the 2025/26 notes:

Current	Next $X{=}0$	Next $X{=}1$	Output $X{=}0$	Output $X{=}1$
A	B	C	0	0
B	D	E	0	0
C	F	G	0	0
D	H	I	0	0
E	J	K	0	0
F	L	M	0	0
G	N	P	0	0
H	A	A	0	0
I	A	A	0	0
J	A	A	0	1
K	A	A	0	0
L	A	A	0	1
M	A	A	0	0
N	A	A	0	0
P	A	A	0	0

Step 1: collapse identical destination rows

Rows H and I are exactly the same in every column. Replace state I with H in the next-state columns, then drop row I. The same logic removes the rows K, M, N, P, which all match H. After these replacements:

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

Both I and the four rows that matched H are gone.

Step 2: collapse rows that became identical

Now row D and row G are identical (both go to H/H with output 0/0). Replace every G in the next-state columns with D and drop row G. Rows E and F are identical too, so replace F with E and drop row F.

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

Step 3: collapse further

Rows J and L are now identical, so replace L with J and drop row L:

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

We started with 15 states (A, B, C, D, E, F, G, H, I, J, K, L, M, N, P) and ended with 7. No further rows match, so row matching has nothing more to give.

What row matching misses

Look at the final table above. Are D and H equivalent? Both output 0 for each input, but their next-state entries differ: D goes to (H, H) while H goes to (A, A). Row matching cannot decide, because the next-state labels are literally different. Yet if H and D really do behave identically in context, both could still be merged.

Row matching is purely syntactic. It never looks beyond the labels. To catch states whose next states differ but are themselves equivalent, you need the implication table, which is the subject of the next note:

Implication Table

This distinction matters in supervision questions and Tripos examples: an implication-table question is one where row matching gets you part of the way but cannot finish the job.