4
$\begingroup$

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?

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Feb 1, 2023 at 21:16
  • 1
    $\begingroup$ 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…) $\endgroup$
    – Rémi
    Feb 1, 2023 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.