等價類與分割（equivalence classes and partitions）

當一個等價關係把一個集合分成「相同」的群組後，每一群叫做一個等價類，而整個切分成互不重疊群組的結果叫做分割。想想整理一籃襪子：每隻襪子按顏色恰好落入一堆，沒有一堆是空的，也沒有襪子同時落在兩堆裡。那些堆就是等價類；所有堆合起來就是分割。

精確地說，元素 x 的等價類常寫作 [x]，是所有與 x 等價的元素構成的集合。在「除以 3 同餘」之下，4 的等價類是 [4] = {…, 1, 4, 7, 10, …}，也就是所有餘數為 1 的數。最關鍵的結構事實是雙向的：每個等價關係都產生一個分割（它的等價類所成的集合），而反過來，集合的每個分割也定義一個等價關係（兩樣東西等價，恰好當它們落在同一個區塊裡）。這些區塊互不相交，且合起來覆蓋整個集合，所以每個元素恰好屬於一個等價類。

這正是狀態合併與 Myhill-Nerode 定理背後的精確機制。把所有會讓一台假想機器走向無法區分之未來的輸入字串歸為一群，每個區塊就成為最小 DFA 的一個狀態；區塊的數目——語言的指數——恰好是辨識它的最小 DFA 的狀態數，而這個數目有限，正好當該語言是正規語言時。於是「這個關係有多少等價類？」就變成了「這個語言根本上需要多少記憶？」。