右不變的等價關係（right-invariant equivalence relation）

右不變性是讓「不可區分關係」在你繼續讀下去時仍表現良好的規則。直覺是：若兩個前綴本來就可互換，那麼在兩者後面「接上同一個下一個符號」必然仍讓它們可互換——多讀一些，絕不該把本來相同的處境弄成不同。具有此性質的關係尊重「往右讀」這個動作，因此稱為「右不變」。

精確地說，Σ（Sigma）上字串的等價關係 ≡ 是右不變的（右同餘），若每當 x ≡ y，就有對 Σ 中每個符號 a 都成立 xa ≡ ya（因而對每個字串 z 都有 xz ≡ yz）。Myhill-Nerode 關係 ≡_L 恰好具備此性質：若 x 與 y 對 L 有相同的未來，則 xa 與 ya 也是，因為 xa 的任何續接 z 不過是 x 的續接 az。這正是讓等價類能當作 DFA 狀態的原因：從某一類出發，讀符號 a 永遠帶你到「單一個、定義良好」的類，這恰恰就是轉移函數 δ（delta）。

右不變性是「靜態、純語言」的關係與「動態、逐步」的機器之間的橋梁。一台 DFA 的可達性也誘導出一個右不變關係（兩個字串相關，若它們把機器帶到同一狀態），而任何「有限指數、且其類尊重 L」的右不變關係都能轉成一台 DFA。Myhill-Nerode 關係是「最粗」的這種關係——它盡可能多地合併——這正是它產生最小機器的原因。