Let $L \subseteq X^{\ast}$ is some language, then we define the syntactic congruence as $$ u \sim v :\Leftrightarrow \forall x, y\in X^{\ast} : xuy \in L \leftrightarrow xvy \in L $$ and the quotient monoid $X^{\ast} / \sim_L$ is called the syntactic monoid of $L$.

Now what monoids arise as syntactic monoids of languages? I found languages for symmetric groups and for the set of all mappings on some underlying finite set. But what about other, are there finite monoids that could not be written as the syntactic monoid of some language?

For a given automaton, by considering the monoid generated by the mappings induced by the letters on the states (the so called transformation monoid) when function composition is read from left to right, it holds that the transformation monoid of the minimal automaton is precisely the syntactic monoid. This observation helped me in constructing the above mentioned examples.

Let me also not that it is quite simple to realise any finite monoid $M$ as the transformation monoid of some automaton, simply take the elements of $M$ as the states, and consider every generator of $M$ as a letter of the alphabet and the transitions are given by $qx$ for some state $q$ and letter $x$, then the transformation monoid is isomorphic to $M$ itself (this is similar to the Cayley theorem about how groups embed into symmetric groups).

Let $L \subseteq X^{\ast}$ be some language, then we define the syntactic congruence as $$ u \sim v :\Leftrightarrow \forall x, y\in X^{\ast} : xuy \in L \leftrightarrow xvy \in L $$ and the quotient monoid $X^{\ast} / \sim_L$ is called the syntactic monoid of $L$.

Now what monoids arise as syntactic monoids of languages? I found languages for symmetric groups and for the set of all mappings on some underlying finite set. But what about other, are there finite monoids that could not be written as the syntactic monoid of some language?

For a given automaton, by considering the monoid generated by the mappings induced by the letters on the states (the so called transformation monoid) when function composition is read from left to right, it holds that the transformation monoid of the minimal automaton is precisely the syntactic monoid. This observation helped me in constructing the above mentioned examples.

Let me also not that it is quite simple to realise any finite monoid $M$ as the transformation monoid of some automaton, simply take the elements of $M$ as the states, and consider every generator of $M$ as a letter of the alphabet and the transitions are given by $qx$ for some state $q$ and letter $x$, then the transformation monoid is isomorphic to $M$ itself (this is similar to the Cayley theorem about how groups embed into symmetric groups).