0
$\begingroup$

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

I am looking for references/applications.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ What do you mean by "convert a monoid into an automaton"? Please give a concrete example. $\endgroup$ – Yuval Filmus May 12 '15 at 14:18
  • $\begingroup$ 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? $\endgroup$ – Michela May 13 '15 at 7:21
  • $\begingroup$ 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? $\endgroup$ – D.W.♦ May 14 '15 at 5:32
3
$\begingroup$

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$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – beroal Feb 10 '18 at 13:56
  • 1
    $\begingroup$ @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)$." $\endgroup$ – J.-E. Pin Feb 10 '18 at 18:10

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