# Is a right invariant equivalent relation necessarily $𝑅_𝑀$ for some finite automaton $𝑀$?

In Ullman's Introduction to Automata, Languages and Computation (1979)

Let $$M = (Q, \Sigma, \delta, q_0, F)$$ be a DFA. Relation $$R_M$$ is defined as: for any $$x$$ and $$y$$ in $$\Sigma^*$$, let $$xR_My$$ if and only if $$\delta(q_0, x) = \delta(q_0, y)$$.

An equivalence relation $$R$$ such that $$xRy$$ implies $$xzRyz$$ is said to be right invariant (with respect to concatenation). We see that every finite automaton induces a right invariant equivalence relation.

Is a right invariant equivalent relation necessarily $$R_M$$ for some finite automaton $$M$$?

Theorem 3.9 (The Myhill-Nerode theorem). The following three statements are equivalent:

1. The set $$L \subseteq \Sigma^*$$ is accepted by some finite automaton.

2. $$L$$ is the union of some of the equivalence classes of a right invariant equivalence relation over $$\Sigma^*$$ of finite index.

3. Let equivalence relation $$R_L$$ over $$\Sigma^*$$ be defined by: $$x R_L y$$ if and only if for all $$z \in \Sigma^*$$, $$xz$$ is in $$L$$ exactly when $$yz$$ is in $$L$$. Then $$R_L$$ is of finite index.

Suppose $$L$$ is a regular language. If $$L$$ is the union of some of the equivalence classes of a right invariant equivalence relation $$R$$ over $$\Sigma^*$$ of finite index, is there some finite machine $$M$$ s.t. $$L$$ is the language which $$M$$ accepts and $$R=R_M$$?

My questions above come from having difficulty understanding what the Myhill-Nerode theorem means.

Thanks.

## 1 Answer

Question 1 . A relation of the form $$R_M$$ for some finite automaton has finite index. So no, a right invariant equivalent relation is not necessarily of the form $$R_M$$: take for instance the equivalence $$\sim$$ defined by $$u \sim v$$ if and only if $$|u| = |v|$$.

Question 2. Let $$L$$ be a regular language of $$A^*$$ which is the union of some of equivalence classes of a right invariant equivalence relation $$R$$ of finite index $$\sim$$. Let $$Q$$ be the (finite) set of $$\sim$$-equivalence classes. For $$q \in Q$$ and $$a \in A$$, let $$q \cdot a$$ be the $$\sim$$-class of $$ua$$ for some $$u \in q$$. This is well-defined, that is, it does not depend on the choice of $$u \in q$$: if $$v \in q$$, then $$u \sim v$$ and hence $$ua \sim va$$.

Since $$L$$ is the union of some $$\sim$$-classes, there is a subset $$F$$ of $$Q$$ such that $$L = \bigcup_{q \in F} q$$. Let $$i$$ be the $$\sim$$-class of the empty word. Then the DFA $${\cal A} = (Q, A, \cdot, i, F)$$ accepts $$L$$ and $${\sim} = R_L = R_{\cal A}$$.