Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 3 / 12I / iv / Solution

Suppose first that $A$ is a regular language, accepted by a deterministic finite automaton $D$. If two words reach the same state, then every continuation is accepted from both or rejected from both. Thus they are equivalent under ${\sim }_A$, and the number of equivalence classes is at most the finite number of states of $D$.

Conversely, suppose ${\sim }_A$ has finitely many classes. Define a deterministic automaton byandThe transition is well defined: if $v{\sim }_{A}w$, then for every suffix $u$,so $va{\sim }_{A}wa$. Likewise, membership in $F$ is independent of the representative by taking the empty suffix in the definition of ${\sim }_A$. Induction givesso the automaton accepts exactly $A$. It has finitely many states, and therefore $A$ is regular. This proves the Myhill-Nerode theorem in the stated formulation. The assumption $\epsilon \notin A$ merely says that the initial state is not accepting.