1
$\begingroup$

One used equivalence relation in regular languages is that for a language $L$ over alphabet $\Sigma$, $(x\sim^Ly)\Leftrightarrow (\forall w\in \Sigma^* xw\in L \Leftrightarrow yw\in L)$.

That means, if two words $x,y$ are not in the same class, there exists $w\in \Sigma^*$ such that $xw\in L$ but $yw \notin L$.

It is implied by Myhill–Nerode theorem, that if we have infinitely many equivalence classes for a language $L$, that $L$ is not a regular language.

My question is this: Is it correct to say that if we have an infinite amount of equivalence classes then there are infinitely many different $w\in \Sigma^*$ that "breaks" such equivalence relation between those classes? If so, how do we prove it? If not, is there a counter-example?

$\endgroup$
  • 1
    $\begingroup$ If $x,y$ are inequivalent, then it doesn't necessarily mean that there exists $w$ such that $xw \in L$ but $yw \notin L$. For example, if $L = 0\Sigma^*$, $x = 1$, and $y = 0$, all $w$ satisfy $xw \notin L$ and $yw \in L$. $\endgroup$ – Yuval Filmus Nov 18 '17 at 15:19
  • $\begingroup$ In your formal definition of the equivalence relation, I think you're missing a comma or something after the $\Sigma^*$. $\endgroup$ – ruakh Nov 18 '17 at 17:46
2
$\begingroup$

Let $L$ be a non-regular language, and suppose that there were only finitely many separating words, say $n$. Construct a graph in which vertices are equivalence classes and the edge $([x],[y])$ (where $x,y$ are the lexicographically first words in their equivalence classes, and $x<y$) is colored by the set of words separating $[x]$ from $[y]$, where for each word $w$ we additionally indicate whether $xw \in L$ ("$w<$") or $yw \in L$ ("$w>$").

Ramsey's theorem states that there exists an infinite monochromatic clique $A$ colored $\chi$. Let $[x],[y],[z] \in A$, where $x < y < z$. We consider two possibilities:

  • If $w< \in \chi$ then we get a contradiction since due to $(x,y)$ we should have $yw \notin L$, whereas due to $(y,z)$ we should have $yw \in L$.

  • If $w> \in \chi$ then we reach a similar contradiction: considering the same edges as before, we should have $yw \in L$ and $yw \notin L$.

The finitary version of Ramsey's theorem shows that for each $n$, there is $N$ such that every language with at least $N$ equivalence classes must have at least $n$ separating words.

$\endgroup$
  • $\begingroup$ I seem to miss the underlying argument. You show that for three lexicographically increasing equivalence classes (defined by the minimal word in each class) $[x],[y],[z]$, $[x],[y]$ and $[y],[z]$ cannot have a common separating "directioned word". This implies there are infinitely many separating words (if this is the main claim, where does Ramsey's theorem come in?). In any case, I interpreted the question as "there exists infinitely many separating words between each two different classes", which I guess you interpreted differently (and perhaps as OP meant). $\endgroup$ – Ariel Nov 18 '17 at 16:12
  • 1
    $\begingroup$ My interpretation was: show that there are infinitely many words $w$ such that $w$ separates two of the classes. You only need a very mild version of Ramsey's theorem, since we only want to find three classes with the same directioned separating word. But applying the mild version isn't any easier than applying the general theorem, given that you are aware of it. $\endgroup$ – Yuval Filmus Nov 18 '17 at 16:15
  • $\begingroup$ Your example in the other answer does work for your interpretation. $\endgroup$ – Yuval Filmus Nov 18 '17 at 16:18
  • $\begingroup$ I see, the existence of a clique follows from the assumption that there only exist finitely many separating directioned words? I wasn't clear on the flow. $\endgroup$ – Ariel Nov 18 '17 at 16:21
  • 1
    $\begingroup$ Right, the number of colors is finite. $\endgroup$ – Yuval Filmus Nov 18 '17 at 16:22
1
$\begingroup$

The answer is no. Consider the language $L=\{0^n1^n | n\in\mathbb{N}\}$. The language is not regular and hence $\{0,1\}^*$ has infinitely many equivalence classes under the relation $\sim^L$. Let $C_1$ be the equivalence class of $01$, and $C_2$ be the equivalence class of $010$, then $\epsilon$ is the only separating suffix between them, since for all $w$ with $|w|>0$ we have $01w,010w\notin L$.

$\endgroup$
  • 1
    $\begingroup$ Isn't $0^k1^{n+k}, 0^k1^{n+1+k}$ is a seperating suffix for each $k\in \mathbb{N}$? $\endgroup$ – Mickey Nov 18 '17 at 14:37
  • $\begingroup$ You are definitely correct, l'll try to fix it shortly. $\endgroup$ – Ariel Nov 18 '17 at 14:52

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.