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).

Experiment

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

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

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