Syntactic monoid

Remarks

Example: for $\Sigma = \set{a}$ and $L = \set{a^{2n} : n \ge 0}$, one has $a^i \equiv_L a^j$ exactly when $i \equiv j \pmod 2$, so $M(L) \cong \Z/2\Z$. Non-example: the one-sided relation $u \sim v$, given by "$uz \in L$ if and only if $vz \in L$ for all $z$", is in general not a congruence. For $L = \set{ab}$, one has $b \sim bb$, since no continuation puts either word in $L$, but $ab \not\sim abb$, since $ab \in L$ and $abb \notin L$. So multiplying on the left by $a$ does not preserve $\sim$, and the classes of $\sim$ do not form a quotient monoid. A monoid $M$ recognizes $L$ when $L = \varphi^{-1}(P)$ for some monoid morphism $\varphi \colon \Sigma^* \to M$ and some $P \subseteq M$. The syntactic monoid recognizes $L$ and divides every monoid that recognizes $L$. The language $L$ is regular if and only if $M(L)$ is finite, and then $M(L)$ is isomorphic to the transition monoid of the minimal DFA of $L$.