正規語言的性質、幫浦引理與最小化
可區分狀態（distinguishable states）
在一台 DFA 內部，兩個狀態是「可區分的」，若存在某個輸入字串，從其中一個出發會導向接受、從另一個出發會導向拒絕。想像你站在一棟建築的兩個不同房間裡：若有一串門，從某一房間走出去到「是」、卻從另一房間走出去到「否」，那這兩個房間就真的不同，必須分開。若不存在這樣的一串門，兩房間行為完全相同，可以合併——它們是「等價的」。
精確地說，在轉移函數為 δ（delta）的 DFA 中，狀態 p 與 q 是可區分的，若存在字串 z，使得從 p 讀 z 停在接受狀態、而從 q 讀 z 停在非接受狀態（或反之）。若不存在這樣的 z，它們就是等價的（不可區分）。有一個俐落的歸納法來找出它：若一個是接受狀態、另一個不是，則兩者「0-可區分」；若某個單一符號 a 把它們送到已經「k-可區分」的狀態，則它們「(k+1)-可區分」。反覆迭代這件事，正是最小化的填表／分割細化步驟。
這是「字串不可區分性」在機器這一側的鏡像。可區分狀態對應到「未來不同」的前綴（不同的 Myhill-Nerode 類），等價狀態對應到可互換的前綴。把所有等價狀態合併，正是最小化所做的事，而剩下的可區分狀態，恰恰就是最小 DFA 必須擁有的狀態。
狀態 p（接受）與 q（非接受）由 z ＝ ε（空字串）區分——什麼都不讀，p 接受而 q 不接受。對「每個」z 都導向相同接受／拒絕判決的狀態，會被併成一個最小 DFA 的狀態。
可區分＝有某個後綴給出不同判決；等價＝沒有任何後綴辦得到。
可區分性是在「一台固定機器」的狀態之間，而 Myhill-Nerode 的不可區分性是在「一個語言」的字串之間——對 DFA 的可達狀態而言兩者一致。基底情形是「空字串」z ＝ ε：一個接受狀態與一個非接受狀態永遠可區分。
又称
另见