0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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}$.

| cite | improve this answer | |
$\endgroup$

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.