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$

1 Answer 1

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .