| dbp:proof
|
- If is regular, construct a minimal DFA to accept it. Clearly, if end up in the same state after running through the DFA, then , thus the number of equivalence classes of is at most the number of DFA states, which must be finite.
Conversely, if has a finite number of equivalence classes, then the state automaton constructed in the theorem is a DFA acceptor, thus the language is regular.
By the construction in .
Given a minimal DFA acceptor , we construct an isomorphism to the canonical one.
Construct the following equivalence relation: if and only if end up on the same state when running through .
Since is an acceptor, if then . Thus each equivalence class is a union of one or more equivalence classes of . Further, since is minimal, the number of states of is equal to the number of equivalence classes of by part . Thus .
Now this gives us a bijection between states of and the states of the canonical acceptor. It is clear that this bijection also preserves the transition rules, thus it is an isomorphism of DFA. The isomorphism is unique, since for both DFA, any state is reachable from the starting state for some word . (en)
|
