# Computing the Syntactic Congruence

The syntactic monoid of a language $L \subseteq X^*$ is defined as the monoid obtained from the congruence relation $$u\ \tilde{}\ 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 tupel $(q_0, q_1, \ldots, q_n)$ corresponds to the identity element of the monoid and the tupels $(q_0, q_1, \ldots, q_n) \cdot x$ for $x \in X$ correspond to the generators of the monoid. Each tupel corresponds to a minimal word, the product of two tupels $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 simple 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 question:

i) Are there other ways without using an automata as intermediate step to compute the syntactic monoid,

ii) This just works for regular languages, how to proceed for non-regular language? (okay for languages like $\{a^nb^n : n \in \mathbb N\}$ one could imagine an infinite automata and proceed, but that does not works in general)

• 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 Jan 8 '14 at 22:25
• 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 Jan 8 '14 at 22:38
• 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 Jan 8 '14 at 22:45
• 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 Jan 8 '14 at 23:07
• 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 (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 Jan 8 '14 at 23:22

Question 1. Yes, there are other ways than using automata. Typically, if you already now 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 $<a,b \mid ab = 1>$.

(4) Let $L = \{a^nb^n \mid n \geqslant 0 \}$. Its syntactic monoid is the monoid with zero presented by $<a,b \mid ba = 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? – StefanH Jan 11 '14 at 13:15
• You are absolutely right. I will update my answer. – J.-E. Pin Jan 11 '14 at 14:15