等價關係（equivalence relation）

等價關係是把「在我們在乎的意義下相同」說得精確的方法，即使這些東西並非字面上一模一樣。兩枚面額相同的硬幣、兩個押韻的字、兩個同年出生的人——每一個都是一種「相同」的判斷，它忽略掉除了你所選特徵以外的一切。重點在於把一大堆雜亂的集合分類成乾淨的群組，群組之內的東西全都算可以互換。

當一個關係 R 同時具備以下三個性質時，它就是等價關係：自反（任何東西都與自己等價，x R x）、對稱（若 x R y 則 y R x）、遞移（若 x R y 且 y R z 則 x R z）。整數上「除以 3 餘數相同」這個日常關係就是完美的例子：4 與 7 等價（餘數都是 1），這個關係顯然在一個數與自己之間成立，它不在乎你先說哪個數，而餘數又可以遞移地串接起來。

這個單一概念是兩個基石性結果背後的引擎。Myhill-Nerode 定理把兩個字串判為等價，當沒有任何後綴能在某語言下把它們區分開；所得群組的數目恰好告訴你最小 DFA 需要多少狀態，而這個數目有限，當且僅當該語言是正規語言。DFA 最小化的做法，就是合併那些在「接受完全相同的未來字串」意義下等價的狀態。在這兩種情形裡，等價關係都把一個無限的字串或狀態集合切成一堆整齊的等價類。