# Building the minimal automaton from the syntactic monoid of a language

I'm studying the algebraic view of automata theory. One of the basic results is that the syntactic monoid of a language $$L$$ is the transition monoid $$M(A)$$ of the minimal automaton $$A(L)$$ accepting $$L$$. It is also very easy, from a monoid $$M$$ and a morphism $$\mu:\Sigma^*\to M$$, to build an equivalent deterministic automaton $$A(M)$$ by using the monoid itself as the set of states and the morphism to build the transition function.

However, if I understand well, $$A(M(L))\ne A(L)$$, i.e. the syntactic monoid is the transition monoid of the minimal automaton, but the automaton I trivially get from the syntactic monoid is not the minimal automaton. Of course, to get $$A(L)$$ one could minimize $$A(M(L))$$, but I wonder if there is a more direct definition or construction.

So if the above is correct, is there a way to get the actual minimal automaton $$A(L)$$ from the syntactic monoid $$M(L)$$, without building $$A(M(L))$$ and then minimize it?

No, we cannot compute $$A(L)$$ from $$M(L)$$ without first building $$A(M(L))$$, essentially because $$A(M(L))$$ is obtained from $$M(L)$$ by forgetting some information; in other words, if you are given $$M(L)$$, then, you know $$A(M(L))$$ without having to do any computation.
• Thanks! I might be wrong but, a quotient of $M(L)$ should be smaller than $M(L)$, right? But then, since $M(L)$ is the smallest monoid recognising $L$, how can it be that the quotient recognises $L$ as well? Feb 1, 2023 at 21:16
• Of course you're right, I've edited my answer. (The problem was that $\sim$ is not a congruence of monoids so $M'$ does not have a structure of monoid…)