字串的不可區分性（indistinguishability of strings）

把「讀一個字串」想成往背包裡裝入你唯一被允許帶往未來的記憶。兩個字串「不可區分」，若它們的背包可以互換：無論你接下來讀什麼後綴，把其中一個前綴換成另一個，都不會改變你最終是否接受。若你無法用任何「未來」把它們分辨開，那麼單一個自動機狀態就能安全地代表兩者。

形式上，固定字母表 Σ（Sigma）上的語言 L。字串 x 與 y 對 L 而言「不可區分」，記作 x ≡_L y，當對 Σ* 中的每一個字串 z，xz 屬於 L 若且唯若 yz 屬於 L。字串 z 稱為「區分用的延伸」或見證；若有某個 z 使 xz、yz 中恰有一個屬於 L，則 x 與 y 是「可區分的」。這正是 Myhill-Nerode 定理背後的等價關係，而它純粹是「語言」的性質——它從不提及任何機器。

不可區分性精確地表達了「這兩個前綴讓自動機處於實際上相同的處境」。這正是最小 DFA 為何能「每類一個狀態」的原因：無法以任何未來輸入分辨的狀態是冗餘的，可以合併。它也是非正規性證明的引擎——若你能造出無窮多個兩兩可區分的字串，該語言就需要無窮多種相異的記憶，而沒有有限機器具備這種能力。