Regular Language Properties, the Pumping Lemma & Minimization

distinguishable states

Inside a DFA, two states are DISTINGUISHABLE if there is some input string that, started from one, leads to acceptance and, started from the other, leads to rejection. Picture standing in two different rooms of a building: if there is a sequence of doors that exits to 'YES' from one room but 'NO' from the other, the rooms are genuinely different and must be kept apart. If no such sequence exists, the rooms behave identically and can be merged — they are EQUIVALENT.

Precisely, in a DFA with transition function δ (delta), states p and q are distinguishable if there exists a string z such that reading z from p ends in an accepting state while reading z from q ends in a non-accepting state (or vice versa). They are equivalent (indistinguishable) if no such z exists. There is a clean inductive way to find this: states are 0-distinguishable if one is accepting and the other is not; they are (k+1)-distinguishable if some single symbol a sends them to states that are already k-distinguishable. Iterating this is exactly the table-filling / partition-refinement step of minimization.

This is the machine-side mirror of string indistinguishability. Distinguishable states correspond to prefixes with different futures (different Myhill-Nerode classes), and equivalent states correspond to prefixes that are interchangeable. Merging all equivalent states is precisely what minimization does, and the leftover distinguishable states are exactly the states the minimal DFA must have.

States p (accepting) and q (non-accepting) are distinguishable by z = ε (the empty string) — read nothing, and p accepts but q does not. States that always lead to the same accept/reject verdict on every z get merged into one minimal-DFA state.

Distinguishable = some suffix gives different verdicts; equivalent = none ever does.

Distinguishability is between states of one fixed machine, whereas Myhill-Nerode indistinguishability is between strings of a language — they coincide for reachable states of a DFA. The base case is the EMPTY string z = ε: an accepting and a non-accepting state are always distinguishable.

Also called
distinguishable vs equivalent statesstate equivalence可區分與等價狀態狀態等價