HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Building the minimal automaton from the syntactic monoid of a language

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
themonoidbuildinglanguageminimalsyntacticfromautomaton

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#157176, answer score: 4

Revisions (0)

No revisions yet.