a right-invariant equivalence relation

Right-invariance is the rule that makes the indistinguishability relation behave well when you keep reading. The intuition: if two prefixes are already interchangeable, then APPENDING the same next symbol to both must keep them interchangeable — reading more should never un-confuse situations that started out identical. A relation with this property respects the act of reading on the right, hence 'right-invariant'.

Precisely, an equivalence relation ≡ on strings over Σ (Sigma) is right-invariant (a right congruence) if whenever x ≡ y, then xa ≡ ya for every symbol a in Σ (and hence xz ≡ yz for every string z). The Myhill-Nerode relation ≡_L has exactly this property: if x and y have the same future with respect to L, then so do xa and ya, because any continuation z of xa is just the continuation az of x. This is what lets the equivalence classes serve as DFA states: from a class, reading symbol a always lands you in a single well-defined class, which is precisely a transition function δ (delta).

Right-invariance is the bridge between the static, language-only relation and the dynamic, step-by-step machine. A DFA's reachability also induces a right-invariant relation (two strings are related if they drive the machine to the same state), and any right-invariant relation of finite index whose classes respect L can be turned into a DFA. The Myhill-Nerode relation is the COARSEST such relation — it merges as much as possible — which is why it yields the smallest machine.