# algoritm to convert a monoid into an automaton [closed]

In literature, is there an algoritm to convert a monoid into an atomaton?

I am looking for references/applications.

• What do you mean by "convert a monoid into an automaton"? Please give a concrete example. – Yuval Filmus May 12 '15 at 14:18
• Let (T , +*) be the commutative monoide defined on {0,1,2} by +*=min{x+y,2}. This monoid can be convert into automata. There is a algoritm? – Michela May 13 '15 at 7:21
• Please edit your question to include all relevant information in the question -- don't just drop material in the comments. Also, you can use Latex to format the mathematics properly. Finally, please specify what you mean by "convert": what property should the automaton have? how should it be related to the monoid? For instance, if my algorithm always outputs the trivial one-state automaton, why doesn't that satisfy the spec? – D.W. May 14 '15 at 5:32

## 1 Answer

Short answer. See the Cayley graph of the monoid as an automaton.

Details. Let $L$ be a language recognised by a finite monoid $M$. Then there is a morphism $\varphi:A^* \rightarrow M$ and a subset $P$ of $M$ such that $L = \varphi^{-1}(P)$. Take the right representation of $A$ on $M$ defined by $s \cdot a = s\varphi(a)$. This defines a deterministic automaton $\mathcal{A} = (M, A, \cdot, 1, P)$. Now, a word $u$ is accepted by $\mathcal{A}$ if and only if $1 \cdot u \in P$. Since $1 \cdot u = \varphi(u)$, this condition means $\varphi(u) \in P$ or $u \in \varphi^{-1}(P)$. Since $L = \varphi^{-1}(P)$, we conclude that $\mathcal{A}$ recognises $L$.

• Hi. I am reading your textbook “Mathematical Foundations of Automata Theory” where your answer appears as Proposition 3.19. Could you clarify, please, what is “the right representation of $A$ on $M$”? I can not find a definition in your textbook or on the web. – beroal Feb 10 '18 at 13:56
• @beroal Just replace this sentence by "Define a deterministic automaton $\mathcal{A} = (M, A, \cdot, 1, P)$, where, for every $s \in M$ and $a \in A$, $s\cdot a = s\varphi(a)$." – J.-E. Pin Feb 10 '18 at 18:10