I am studying finite state automata and learning how to prove a machine uses the minimum number of states. I have come across the Myhill-Nerode theorem and one of the corollaries states the following

Corollary. For a deterministic finite automaton M, the minimum number of states in any equivalent deterministic finite automaton is the same as the number of equivalence classes of M's states.

My question is, what does "equivalence classes of M's states" mean?

Thank you for your time!


Two states are equivalent if they accept the same language. An equivalence class is therefore a set of states that all accept the same language (and no other state in the automaton does). In particular in a minimal autommaton, all states accept different languages, so each state is alone in its equivalence class.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.