<p><strong>Question 1</strong>. Yes, there are other ways than using automata. Typically, if you already know that your language is recognized by some surjective monoid morphism <span class="math-container">$\varphi: A^* \to M$</span>, then you know that <span class="math-container">$M(L)$</span> (the syntactic monoid of <span class="math-container">$L$</span>) is a quotient of <span class="math-container">$M$</span>. For instance if <span class="math-container">$L = \{ u \in \{a,b\}^* \mid |u|_a \equiv 5 \bmod 13 \text{ and } |u|_a \equiv 6 \bmod 7\}$</span>, then you can prove directly that <span class="math-container">$M(L) = \mathbb{Z}/91\mathbb{Z}$</span> without computing the minimal automaton.</p>
<p><strong>Question 2</strong>. C. Brand is right. You can still use the minimal automaton, even if it is infinite. You can also just use the definition of the syntactic congruence to get a presentation of the syntactic monoid. You may also just guess a morphism recognizing your language. Three examples:</p>
<p>(1) Let <span class="math-container">$L = \{u \in \{a,b\}^* \mid |u|_a = |u|_b \}$</span>. Then the morphism <span class="math-container">$\pi: \{a,b\}^* \to \mathbb{Z}$</span> defined by <span class="math-container">$\pi(a) = 1$</span> and <span class="math-container">$\pi(b) = -1$</span> recognizes <span class="math-container">$L$</span> since <span class="math-container">$L = \pi^{-1}(0)$</span>. Thus <span class="math-container">$M(L)$</span> is a quotient of <span class="math-container">$\mathbb{Z}$</span>. But every nontrivial quotient of <span class="math-container">$\mathbb{Z}$</span> is finite and cannot be equal to <span class="math-container">$M(L)$</span> (otherwise <span class="math-container">$L$</span> would be regular). Thus
<span class="math-container">$M(L) = \mathbb{Z}$</span>.</p>
<p>(2) Let <span class="math-container">$L = \{u \in \{a,b\}^* \mid |u|_a \geqslant |u|_b \}$</span>. This context-free language generated by the grammar <span class="math-container">$S \to SS + aSb + 1$</span>. Its syntactic monoid is also equal to <span class="math-container">$\mathbb{Z}$</span>, since <span class="math-container">$L = \pi^{-1}([0, + \infty[)$</span>.</p>
<p><strong>Update following Stefan's comment</strong></p>
<p>(3) Let <span class="math-container">$D$</span> be the Dyck language (see Stefan's comment). Its syntactic monoid is the <em>bicyclic monoid</em>, which is the monoid presented by <span class="math-container">$\langle a,b \mid ab = 1\rangle$</span>.</p>
<p>(4) Let <span class="math-container">$L = \{a^nb^n \mid n \geqslant 0 \}$</span>. Its syntactic monoid is the monoid with zero presented by <span class="math-container">$\langle a,b \mid ba = 0\rangle$</span>.</p>

CC BY-SA 3.0
2014-01-11T13:15:02.630Z
thanks for this very enlightening answer! But one question left, guess $abab = 1$ in the bicyclic monoid, so that $abab$ would also be in the inverse image of $1$ under any homomorphism, so $L = \{ a^n b^n : n \ge 0 \}$ would be to restrictive, but the entire Dyck language $D = \{ w \in \{a,b\}^* : \mbox{for all prefixes $u$ of $w$ is } |u|_b \ge |u|_a \land |w|_a = |w|_b \}$ would fit, or does I overlook something?
StefanH
CC BY-SA 3.0
2014-01-11T14:15:58.990Z
You are absolutely right. I will update my answer.
J.-E. Pin
CC BY-SA 4.0
2014-01-10T11:46:47.333Z
2023-01-28T16:03:42.373Z
2023-01-28T16:03:42.373Z
J.-E. Pin
<p>The <a href="http://en.wikipedia.org/wiki/Syntactic_monoid" rel="nofollow noreferrer">syntactic monoid</a> of a language <span class="math-container">$L \subseteq X^*$</span> is defined as the monoid obtained from the congruence relation
<span class="math-container">$$
 u\ \sim v \ \mbox{ iff }\ \forall x,y \in X^* : xuy \in L \leftrightarrow xvy \in L.
$$</span>
How to compute this in general? For regular languages I just know an approach via the minimal automaton, from which you compute the transition monoid. More concretely let <span class="math-container">$\mathcal A = (X, Q, f, q_0, F)$</span> a DFA, from the state vector <span class="math-container">$(q_0, q_1, \ldots, q_n)$</span> compute the closure with regard to
<span class="math-container">$$ 
 (q_0, q_1, \ldots, q_n) \cdot w = (f(q_0,w), f(q_1, w), \ldots, f(q_n,w))
$$</span>
and <span class="math-container">$w \in X^*$</span>. Then the tuple <span class="math-container">$(q_0, q_1, \ldots, q_n)$</span> corresponds to the identity element of the monoid and the tuples <span class="math-container">$(q_0, q_1, \ldots, q_n) \cdot x$</span> for <span class="math-container">$x \in X$</span> correspond to the generators of the monoid. Each tuple corresponds to a minimal word, the product of two tuples <span class="math-container">$q, q'$</span> is defined by taking some word <span class="math-container">$w$</span> which represents <span class="math-container">$q'$</span> and compute <span class="math-container">$q\cdot w$</span> (this works because <span class="math-container">$[u] = [v]$</span> iff <span class="math-container">$f(q,u) = f(q,v)$</span> for all <span class="math-container">$q$</span> in the minimal automata). Or more simply, set <span class="math-container">$f_w(q) := f(q,w)$</span>, then <span class="math-container">$f_u(f_v(q)) = f_{vu}(q)$</span>, the transition monoid is <span class="math-container">$\{ f_w : w \in X^* \}$</span> under functional composition.</p>
<p>Two questions:</p>
<ol>
<li>Are there other ways without using an automata as intermediate step to compute the syntactic monoid?</li>
<li>This just works for regular languages, how to proceed for non-regular language? (For languages like <span class="math-container">$\{a^nb^n : n \in \mathbb N\}$</span> one could imagine an infinite automaton and proceed, but that does not works in general.)</li>
</ol>

CC BY-SA 3.0
2014-01-08T22:25:02.757Z
ad ii): Why doesn't this work in general? You can give an infinite automaton for any language and thus also obtain the corresponding transition monoid
Cornelius Brand
CC BY-SA 3.0
2014-01-08T22:38:40.690Z
For i), the syntactic monoid and the transition monoid of the minimal deterministic automaton are isomorphic; computing one is the same as computing the other, hence basically computing the automaton.
For ii), if your language is nonregular, the syntactic monoid will be infinite; what is the representation of the syntactic you have in mind in this case?  As a side question: why would you need the syntactic monoid of a nonregular language?
Michaël Cadilhac
CC BY-SA 3.0
2014-01-08T22:45:32.343Z
Let me clarify why I'm asking where is your interest for syntactic monoids of nonregular language.  The syntactic monoid of $\{a^nb^n\}$ is isomorphic to $\mathbb{Z}$, which recognizes undecidable languages in the general case.  Lots of proposals exist for "fixing" this, but the concept of *syntactic monoid* has to be somehow refined.
Michaël Cadilhac
CC BY-SA 3.0
2014-01-08T23:07:46.063Z
I had no special application in mind, but just was curious. Your statement about the syntactic monoid $\mathbb Z$ sounds interesting and it's connection to undecidable languages, do you know any references where I can read further?
StefanH
CC BY-SA 3.0
2014-01-08T23:22:58.127Z
There are multiple attempts at a finer syntactic monoid hierarchy — one usual goal being to allow for nonclosure under complement.  J.-É. Pin has these incredibly nice *positive varieties* and also a topological approach (http://www.math.ru.nl/~mgehrke/GGP10.pdf), J. Sakarovitch started the use of *pointed monoids*, and A. Krebs introduced *typed monoids*.  The latter tool is able to characterize TC$^0$.
Michaël Cadilhac
CC BY-SA 3.0
2014-01-08T23:53:04.267Z
Thank you! I have another question pending w.r.t. to ordered syntactic monoids (the generalisation to nonclosure under complement), maybe you like to take a look: http://cstheory.stackexchange.com/questions/20507/the-polynomial-languages-and-ordered-syntactic-monoids
StefanH
CC BY-SA 3.0
2014-01-09T00:50:05.637Z
Your computation problem is not well-defined: how do you give a language to your algorithm? and how does it answers with the monoid if it is infinite? If you give the language via Turing Machine then any question about the syntactic monoid of the language is undecidable, by Rice theorem.
Denis
CC BY-SA 3.0
2014-01-09T08:57:31.300Z
@Stefan: Ahah, too late, dkuper went to the rescue :-)  If you read part or all of the pointers I gave you, you may consider yourself up to speed with this field of research, and may provide a good answer for your own question! "Sharing knowledge, Q&A style," as they say!
Michaël Cadilhac
<fl.formal-languages><automata-theory>
Computing the Syntactic Congruence
StefanH
# Computing the Syntactic Congruence

(Asked by: username_0 on 2014-01-08)

The [syntactic monoid](http://en.wikipedia.org/wiki/Syntactic_monoid) of a language $L \subseteq X^\*$ is defined as the monoid obtained from the congruence relation
$$
u\ \sim v \ \mbox{ iff }\ \forall x,y \in X^\* : xuy \in L \leftrightarrow xvy \in L.
$$
How to compute this in general? For regular languages I just know an approach via the minimal automaton, from which you compute the transition monoid. More concretely let $\mathcal A = (X, Q, f, q\_0, F)$ a DFA, from the state vector $(q\_0, q\_1, \ldots, q\_n)$ compute the closure with regard to
$$
(q\_0, q\_1, \ldots, q\_n) \cdot w = (f(q\_0,w), f(q\_1, w), \ldots, f(q\_n,w))
$$
and $w \in X^\*$. Then the tuple $(q\_0, q\_1, \ldots, q\_n)$ corresponds to the identity element of the monoid and the tuples $(q\_0, q\_1, \ldots, q\_n) \cdot x$ for $x \in X$ correspond to the generators of the monoid. Each tuple corresponds to a minimal word, the product of two tuples $q, q'$ is defined by taking some word $w$ which represents $q'$ and compute $q\cdot w$ (this works because $[u] = [v]$ iff $f(q,u) = f(q,v)$ for all $q$ in the minimal automata). Or more simply, set $f\_w(q) := f(q,w)$, then $f\_u(f\_v(q)) = f\_{vu}(q)$, the transition monoid is $\{ f\_w : w \in X^\* \}$ under functional composition.

Two questions:

1. Are there other ways without using an automata as intermediate step to compute the syntactic monoid?
2. This just works for regular languages, how to proceed for non-regular language? (For languages like $\{a^nb^n : n \in \mathbb N\}$ one could imagine an infinite automaton and proceed, but that does not works in general.)

**Tags:** fl.formal-languages, automata-theory

> **Comments:**
> **username_1**: ad ii): Why doesn't this work in general? You can give an infinite automaton for any language and thus also obtain the corresponding transition monoid  
> **username_2**: For i), the syntactic monoid and the transition monoid of the minimal deterministic automaton are isomorphic; computing one is the same as computing the other, hence basically computing the automaton. For ii), if your language is nonregular, the syntactic monoid will be infinite; what is the representation of the syntactic you have in mind in this case?  As a side question: why would you need the syntactic monoid of a nonregular language?  
> **username_2**: Let me clarify why I'm asking where is your interest for syntactic monoids of nonregular language.  The syntactic monoid of $\{a^nb^n\}$ is isomorphic to $\mathbb{Z}$, which recognizes undecidable languages in the general case.  Lots of proposals exist for "fixing" this, but the concept of *syntactic monoid* has to be somehow refined.  
> **username_0**: I had no special application in mind, but just was curious. Your statement about the syntactic monoid $\mathbb Z$ sounds interesting and it's connection to undecidable languages, do you know any references where I can read further?  
> **username_2**: There are multiple attempts at a finer syntactic monoid hierarchy — one usual goal being to allow for nonclosure under complement.  J.-É. Pin has these incredibly nice *positive varieties* and also a topological approach (http://www.math.ru.nl/~mgehrke/GGP10.pdf), J. Sakarovitch started the use of *pointed monoids*, and A. Krebs introduced *typed monoids*.  The latter tool is able to characterize TC$^0$.  
> **username_0**: Thank you! I have another question pending w.r.t. to ordered syntactic monoids (the generalisation to nonclosure under complement), maybe you like to take a look: http://cstheory.stackexchange.com/questions/20507/the-polynomial-languages-and-ordered-syntactic-monoids  
> **username_3**: Your computation problem is not well-defined: how do you give a language to your algorithm? and how does it answers with the monoid if it is infinite? If you give the language via Turing Machine then any question about the syntactic monoid of the language is undecidable, by Rice theorem.  
> **username_2**: @Stefan: Ahah, too late, dkuper went to the rescue :-)  If you read part or all of the pointers I gave you, you may consider yourself up to speed with this field of research, and may provide a good answer for your own question! "Sharing knowledge, Q&A style," as they say!  

---

## 1 answers

### Answer by username_4 on 2014-01-10. Score: 7 | Accepted answer

**Question 1**. Yes, there are other ways than using automata. Typically, if you already know that your language is recognized by some surjective monoid morphism $\varphi: A^\* \to M$, then you know that $M(L)$ (the syntactic monoid of $L$) is a quotient of $M$. For instance if $L = \{ u \in \{a,b\}^\* \mid |u|\_a \equiv 5 \bmod 13 \text{ and } |u|\_a \equiv 6 \bmod 7\}$, then you can prove directly that $M(L) = \mathbb{Z}/91\mathbb{Z}$ without computing the minimal automaton.

**Question 2**. C. Brand is right. You can still use the minimal automaton, even if it is infinite. You can also just use the definition of the syntactic congruence to get a presentation of the syntactic monoid. You may also just guess a morphism recognizing your language. Three examples:

(1) Let $L = \{u \in \{a,b\}^\* \mid |u|\_a = |u|\_b \}$. Then the morphism $\pi: \{a,b\}^\* \to \mathbb{Z}$ defined by $\pi(a) = 1$ and $\pi(b) = -1$ recognizes $L$ since $L = \pi^{-1}(0)$. Thus $M(L)$ is a quotient of $\mathbb{Z}$. But every nontrivial quotient of $\mathbb{Z}$ is finite and cannot be equal to $M(L)$ (otherwise $L$ would be regular). Thus
$M(L) = \mathbb{Z}$.

(2) Let $L = \{u \in \{a,b\}^\* \mid |u|\_a \geqslant |u|\_b \}$. This context-free language generated by the grammar $S \to SS + aSb + 1$. Its syntactic monoid is also equal to $\mathbb{Z}$, since $L = \pi^{-1}([0, + \infty[)$.

**Update following Stefan's comment**

(3) Let $D$ be the Dyck language (see Stefan's comment). Its syntactic monoid is the *bicyclic monoid*, which is the monoid presented by $\langle a,b \mid ab = 1\rangle$.

(4) Let $L = \{a^nb^n \mid n \geqslant 0 \}$. Its syntactic monoid is the monoid with zero presented by $\langle a,b \mid ba = 0\rangle$.

> **Comments:**
> **username_0**: thanks for this very enlightening answer! But one question left, guess $abab = 1$ in the bicyclic monoid, so that $abab$ would also be in the inverse image of $1$ under any homomorphism, so $L = \{ a^n b^n : n \ge 0 \}$ would be to restrictive, but the entire Dyck language $D = \{ w \in \{a,b\}^* : \mbox{for all prefixes $u$ of $w$ is } |u|_b \ge |u|_a \land |w|_a = |w|_b \}$ would fit, or does I overlook something?  
> **username_4**: You are absolutely right. I will update my answer.  

---

