Myhill–Nerode — the algebra of suffixes

Parent: regular-equivalences

A characterization of regularity by how many "futures" the prefixes have, and the source of the unique minimal DFA.

Indistinguishability

For a language L, two strings are equivalent, x ≡ y, iff they have the same continuations: for every z, xz∈L ⟺ yz∈L.

Myhill–Nerode

L is regular iff ≡ has finitely many classes, and that number equals the state count of the unique minimal DFA.

Why: the classes are the states. A minimal DFA can't distinguish x from y unless some suffix z separates them — so its states are exactly the ≡-classes; anything coarser is wrong, anything finer is redundant. This makes the minimal DFA canonical (unlike regex or NFA, which have no canonical form).

The cleanest non-regularity proof

aⁿbⁿ: the prefixes a⁰, a¹, a², … are pairwise distinguishable — aⁱ and aʲ are separated by the suffix bⁱ (aⁱbⁱ∈L, aʲbⁱ∉L). Infinitely many classes ⇒ not regular. No pumping-lemma bookkeeping needed — you just exhibit an infinite family of distinguishable prefixes. This is usually the right tool for proving a language isn't regular.