[Solved]: Give an example of a language whose Myhill-Nerode equivalence relation is such that if $x,y \in \{0,1\}^*$ with $x \neq y$, then $[x] \neq [y]$

Problem Detail: 

Suppose $\Sigma = \{0,1\}$. Provide an example of a language $L \subseteq \Sigma^*$ with the property that its associated Myhill-Nerode equivalence relation, $R_L$, is such that every one of its equivalence classes is a singleton set; that is, if $x,y \in \Sigma^*$ with $x \neq y$, then $[x] \neq [y]$, where $[x]$ and $[y]$ are equivalence classes with representative elements $x$ and $y$, respectively.

I suspect that this language cannot be regular, since the index of $R_L$ is infinite.

Asked By : David Smith

Answered By : sdcvvc

Consider the language $L$ consisting of words $w a 0 1^n$ where $w$ is an arbitrary word, $a$ is either 0 or 1, $w$ has at least $n$ letters and the $n$-th letter of $w$ is $a$. Clearly, given a word in $L$ there exists exactly one decomposition to this form (define $n$ to be the number of trailing ones in the string).

If $w \neq u$ then without loss of generality $w_i = 0, u_i = 1$ for some $i$. But then $w 0 0 1^i \in L$ while $u 0 0 1^i \notin L$. If $w$ is a prefix of $u$, then you can take $n$ which is larger than the length of $w$ but smaller than length of $u$.

In other words $L=\{v a u a 0 1^n : |v| = n-1, |a| = 1\}$; clearly this is a CFL.

(This is a variant of my answer from Can a language have $\Sigma^{*}$ as its syntactic monoid?)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/31995

3.2K people like this

 Download Related Notes/Documents