<p>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]$)</p>

CC BY-SA 3.0
2011-09-20T18:50:25.773Z
Thanks a lot. I have yet to prove that $\cdot$ is well-defined, but now I see it shouldn't be too difficult.
Janoma
CC BY-SA 3.0
2013-08-28T13:10:55.927Z
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
CC BY-SA 3.0
2011-09-20T18:32:31.307Z
2011-09-20T18:32:31.307Z
Marcin Kotowski
<p>In order to characterize regular languages one finds the following definition useful:</p>

<blockquote>
  <p>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$.</p>
</blockquote>

<p>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.</p>

<p>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.</p>

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

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

<blockquote>
  <p>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$.</p>
</blockquote>

<p>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!</p>

CC BY-SA 3.0
2011-09-20T16:29:47.313Z
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
CC BY-SA 3.0
2011-09-20T16:44:49.563Z
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
CC BY-SA 3.0
2011-09-20T17:06:13.337Z
You may be interested in http://cstheory.stackexchange.com/questions/194/compared-growth-of-the-number-of-syntactic-classes-and-nerode-classes BTW.
Michaël Cadilhac
CC BY-SA 3.0
2011-09-20T18:04:36.727Z
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
<fl.formal-languages><algebra><regular-language>
On the relation for the Myhill-Nerode theorem/syntactic monoid of a language
Janoma
# On the relation for the Myhill-Nerode theorem/syntactic monoid of a language

(Asked by: username_0 on 2011-09-20)

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!

**Tags:** fl.formal-languages, algebra, regular-language
> **Comments:**
> **username_1**: 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".  
> **username_0**: 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.  
> **username_1**: You may be interested in http://cstheory.stackexchange.com/questions/194/compared-growth-of-the-number-of-syntactic-classes-and-nerode-classes BTW.  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_2 on 2011-09-20. Score: 10 | Accepted answer

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]$)

> **Comments:**
> **username_0**: Thanks a lot. I have yet to prove that $\cdot$ is well-defined, but now I see it shouldn't be too difficult.  
> **username_3**: 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.  

---

