the index of a language
The index of a language is a single number that measures exactly how much memory it takes to recognize that language. Picture sorting all possible prefixes into bins, where two prefixes go in the same bin precisely when they are indistinguishable — interchangeable with respect to all futures. The number of bins is the index. A small index means the language is forgetful and easy; an infinite index means it demands unbounded memory and so cannot be regular.
Formally, the index of L is the number of equivalence classes of the Myhill-Nerode relation ≡_L on Σ* (Sigma-star) — that is, the count of distinct 'futures' a prefix can have. The Myhill-Nerode theorem ties this number directly to machines: L is regular exactly when its index is finite, and in that case the index EQUALS the number of states in the minimal DFA. So the index is not just a yes/no test for regularity; it is the precise, machine-independent state count of the best possible recognizer.
This makes the index a sharp lower-bound tool. If you can show a language forces at least k pairwise-distinguishable prefixes, then ANY DFA for it needs at least k states — no clever engineering can do better. And if you can show it forces infinitely many, the language is non-regular, full stop. The index turns a fuzzy question ('how complex is this language?') into a countable invariant of the language itself.
L = 'even number of a's' has index 2 (prefixes split into even-so-far and odd-so-far), so its minimal DFA has 2 states. L = a^n b^n has infinite index (a^0, a^1, a^2, ... are all pairwise distinguishable), so it is not regular.
Finite index = state count of the minimal DFA; infinite index = not regular.
The index is the EXACT minimal state count, not merely an estimate — it is achieved, and it cannot be beaten. A DFA with more states than the index simply has indistinguishable states waiting to be merged.