3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Deleted my answer and updated the title to emphasize the fact that $\Sigma$ is not a unary alphabet, since this is an important element of the question. $\endgroup$ – Patrick87 Oct 16 '14 at 22:39
  • $\begingroup$ A quick note; whatever language you find, it definitely won't be regular, as you correctly suspect. I wasn't able to think of one and have to run now. $\endgroup$ – Patrick87 Oct 16 '14 at 22:45
5
$\begingroup$

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?)

$\endgroup$
2
$\begingroup$

A random language $L$ satisfies this property almost surely. Indeed, consider any two $x,y \in \Sigma^*$. For every $z \in \Sigma^*$, the probability that $xz \in L \Leftrightarrow yz \in L$ is $1/2$, so almost surely $xz \in L \not\Leftrightarrow yz \in L$ for some $z$. That is, any two $x,y \in \Sigma^*$ are inequivalent modulo $L$ almost surely. Since there are only countably many pairs $x,y \in \Sigma^*$, all of them are inequivalent modulo $L$ almost surely.

We can "derandomize" this construction using diagonalization. Let $(x_1,y_1),(x_2,y_2),\ldots$ be some enumeration of all pairs of different words in $\Sigma^*$. We define sets of words $A_n,B_n$ inductively; for each $n$, $A_n$ and $B_n$ will be disjoint finite sets, and $A_n \supseteq A_{n-1}$, $B_n \supseteq B_{n-1}$. The base case is $A_0 = B_0 = \emptyset$. Given $A_{n-1},B_{n-1}$, let $w$ be some word such that $x_nw \notin B_{n-1}$ and $y_nw \notin A_{n-1}$, and define $A_n = A_{n-1} \cup \{x_nw\}$ and $B_n = B_{n-1} \cup \{y_nw\}$; such a word $w$ exists since $A_{n-1},B_{n-1}$ are finite. Let $A = \bigcup_{n \geq 0} A_n$ and $B = \bigcup_{n \geq 0} B_n$, and note that $A,B$ are disjoint. The language $L = A$ separates every pair of words.

$\endgroup$
0
$\begingroup$

The language of palindromes over a non-unary alphabet is a nice example. See for example this question.

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