Computing the Syntactic Congruence

Question

The 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.)

Answer 1

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$.