= 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 by
$$
Q=\Sigma^*/{\sim_A},
\qquad
q_0=[\varepsilon],
\qquad
\delta([w],a)=[wa],
$$
and
$$
F=\{[w]:w\in A\}.
$$
The transition is well defined: if $v\sim_Aw$, then for every suffix $u$,
$$
vau\in A\Longleftrightarrow wau\in A,
$$
so $va\sim_Awa$. Likewise, membership in $F$ is independent of the representative by taking the empty suffix in the definition of $\sim_A$. Induction gives
$$
\widehat\delta([\varepsilon],w)=[w],
$$
so 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 $\varepsilon\notin A$ merely says that the initial state is not accepting.
Back to article page
