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$
2
  • 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$ Nov 18, 2017 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, 2017 at 17:46

2 Answers 2

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$
7
  • $\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, 2017 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$ Nov 18, 2017 at 16:15
  • $\begingroup$ Your example in the other answer does work for your interpretation. $\endgroup$ Nov 18, 2017 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, 2017 at 16:21
  • 1
    $\begingroup$ Right, the number of colors is finite. $\endgroup$ Nov 18, 2017 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$
2
  • 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, 2017 at 14:37
  • $\begingroup$ You are definitely correct, l'll try to fix it shortly. $\endgroup$
    – Ariel
    Nov 18, 2017 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.