語言的指數（index of a language）

語言的指數是一個單一數字，恰好衡量辨識該語言需要多少記憶。想像把所有可能的前綴分裝進箱子，兩個前綴入同一箱，正好當它們不可區分——對所有未來都可互換。箱子的數目就是指數。指數小代表語言「健忘」而容易；指數無窮代表它需要無界記憶，因此不可能是正規的。

形式上，L 的指數是 Myhill-Nerode 關係 ≡_L 在 Σ*（Sigma-star）上的等價類數目——也就是一個前綴可能擁有的相異「未來」的個數。Myhill-Nerode 定理把這個數字直接綁到機器上：L 是正規的，正好當它的指數有限；而在那種情形下，指數「等於」最小 DFA 的狀態數。所以指數不只是正規性的是非測試；它是「最佳可能辨識器」的、與機器無關的精確狀態數。

這讓指數成為一把鋒利的「下界」工具。若你能證明某語言逼出至少 k 個兩兩可區分的前綴，那麼「任何」辨識它的 DFA 都至少需要 k 個狀態——再巧的工程也無法更省。而若你能證明它逼出無窮多個，該語言便是非正規的，沒得商量。指數把一個模糊的問題（「這語言有多複雜？」）變成語言本身的一個可數不變量。