If there are finite number of equivalence classes then L is regular.

Proof

• Let each equivalence class be a state.
• Start state will be .
• Transition Function
• Final states will be those equivalence classes which are subsets of L.
• Now, iff .
• This is a finite automata accepting L.

e.g.

This construction yields the minimum FA

The number of states can not be fewer, because strings belonging to different equivalence classes must take the FA to different states.