# On the relation for the Myhill-Nerode theorem/syntactic monoid of a language

In order to characterize regular languages one finds the following definition useful:

Let $\Sigma$ be an alphabet and $L\subseteq\Sigma^*$. Say that $x,y\in\Sigma^*$ are $\equiv_L$-related, and write $x\equiv_L y$ if for all $z\in\Sigma^*$, $xz\in L$ if and only if $yz\in L$.

This is useful because $\equiv_L$ is an equivalence relation for every language $L$, and a language is regular if and only if the index of $\equiv_L$ (that is, the number of equivalence classes) is finite, as per Myhill-Nerode.

Now, I would like to define a binary operation $\cdot$ on $\Sigma^*_{/\equiv_L}$ as: $[x]\cdot[y]=[xy]$, where $[x]$ is the $\equiv_L$-equivalence class of $x$. This $\cdot$ will be operation that will give $\Sigma^*_{/\equiv_L}$ the structure of a monoid.

My question is: Is $\cdot$ well defined for an arbitrary language? How do I prove it?

So far, my approach has been trying to prove that the definition above is equivalent to:

Let $\Sigma$ be an alphabet and $L\subseteq\Sigma^*$. Say that $x,y\in\Sigma^*$ are $\sim_L$-related, and write $x\sim_L y$ if for all $w,z\in\Sigma^*$, $wxz\in L$ if and only if $wyz\in L$.

This is simple for regular languages, since one can take a minimal DFA and analyze its behaviour with strings that are $\sim_L$-related, but I'm struggling with a general proof. Maybe I'm missing something really simple, but in the paper where I found the "definition" of syntactic monoid, they just take $\Sigma_{/\equiv_L}$ and say "this is the monoid" without specifying the operation, and now that I'm trying to do it with full detail I'm completely stuck. Thanks in advance for your help!

• By well-defined, do you mean $[x] = [y]$ implies, for all class $[z]$ that $[xz] = [yz]$ and $[zx] = [zy]$? This is clear for the first one, but the second one may be false. The second definition you give (with $\sim$) is the usual one and leads to a "well-defined" monoid. They are not "equivalent". – Michaël Cadilhac Sep 20 '11 at 16:29
• By well-defined I mean it doesn not depend on the representatives that I choose to write the classes. I'm starting to think they are not equivalent (working on an example right now), but in that case, it's a bit surprising that both versions are used indistinctly in different books and papers. – Janoma Sep 20 '11 at 16:44
• You may be interested in cstheory.stackexchange.com/questions/194/… BTW. – Michaël Cadilhac Sep 20 '11 at 17:06
• Thanks Michaël! So yes, I also found an example that shows they are different relations. I will try to see if the monoid is immediately well-defined when considering $\sim_L$, and maybe I will change the statement of my question. – Janoma Sep 20 '11 at 18:04

The syntactic monoid of a language $L$, which is $\Sigma^{\ast}$ quotiented by $\sim_{L}$, is usually bigger than the set of equivalence classes of $\Sigma^{\ast}$ quotiented by $\equiv_{L}$. Informally, the Myhill-Nerode relation $\equiv_L$ only cares about the prefixes of a word $w$ (since it reflects the processing of $w$ by a DFA), while the syntactic monoid has to encode the information about all possible infixes of $w$ (otherwise you won't get the algebraic structure $[x]\cdot[y]=[x \cdot y]$)
• Thanks a lot. I have yet to prove that $\cdot$ is well-defined, but now I see it shouldn't be too difficult. – Janoma Sep 20 '11 at 18:50
• Actually, if $|\Sigma^*/{\equiv_L}| = n$, then $|\Sigma^*/{\sim_L}| \leqslant n^n$, and this upper bound can be reached on a three-letter alphabet. – J.-E. Pin Aug 28 '13 at 13:10