Myhill–Nerode Distinguishing Suffixes

Visualize how to prove two DFA states are distinct by finding a short binary suffix that leads one state to an accept state and the other to a reject state.

Myhill–Nerode Distinguishing Suffixes

The Myhill–Nerode theorem provides a way to prove that a language is regular or not, and gives the unique minimum number of states for a DFA recognizing that language. Two strings are equivalent if appending any suffix to both always yields the same acceptance status. Conversely, two strings (or DFA states) are distinguishable if there exists a distinguishing suffix that leads one to an accepting state and the other to a rejecting state. This module explores distinguishing suffixes for languages of binary strings representing numbers divisible by an odd modulus (3, 5, or 7).

Worked Example

Let's consider the language of binary strings whose numeric value is divisible by m = 3. The DFA states correspond to the remainders mod 3 (0, 1, and 2), with state 0 being the only accepting state. The transition for reading a bit b in state r is (2r + b) (mod m). Suppose we want to distinguish state r_1 = 1 and state r_2 = 2.

We search for a suffix using Breadth-First Search (BFS) to find the shortest string. We start with the empty suffix ε.

Length 0 (Empty suffix):
For r_1 = 1: State is 1 (Rejecting)
For r_2 = 2: State is 2 (Rejecting)
Both reject. We continue.
Length 1 (Suffix "0"):
For r_1 = 1: Next is (2(1) + 0) (mod 3) = 2 (Rejecting)
For r_2 = 2: Next is (2(2) + 0) (mod 3) = 1 (Rejecting)
Both reject.
Length 1 (Suffix "1"):
For r_1 = 1: Next is (2(1) + 1) (mod 3) = 0 (Accepting)
For r_2 = 2: Next is (2(2) + 1) (mod 3) = 2 (Rejecting)
One accepts, the other rejects! Thus, "1" is a distinguishing suffix.

The length of this suffix is 1. The final remainder for state 1 is 0, and the final remainder for state 2 is 2.

State 1 --"1"--> State 0 (Accept) State 2 --"1"--> State 2 (Reject)

Experiment

In the interactive module, you can explore the transitions for different moduli (3, 5, 7) and different starting states.

Use the Modulus control to select the modulus.
Use the First remainder control to select the first state.
Use the Second remainder control to select the second state.
Observe the Distinguishing suffix and the resulting Status.

You can test this yourself in the interactive module: Myhill-Nerode Distinguishing Suffixes.

Limitations

This specific method for bounding and guaranteeing the existence of a distinguishing suffix relies on the fact that 2 is invertible modulo m for odd moduli (3, 5, 7). For even moduli, multiplying by 2 causes a loss of information (it is not a bijection), which means some distinct states might not be distinguishable by any suffix, leading to equivalent states even if the remainders differ. Thus, this proof does not generalize to even m. Furthermore, the algorithm bounds the search length since the state space is bounded by the modulus m.

References

For more information on the Myhill-Nerode Theorem, you can read the following handout:

Myhill-Nerode Theorem - Columbia University

Myhill–Nerode Distinguishing Suffixes