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:
- Are there other ways without using an automata as intermediate step to compute the syntactic monoid?
- 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.)