# automaton over a monoid

Recall that a semiautomaton $A$ can be visually represented by a directed graph^{} ${G}_{A}$, whose vertices (or nodes) are states of $A$, and whose edges are labeled by elements from the input alphabet $\mathrm{\Sigma}$ of $A$. Labeling can be extended to paths of ${G}_{A}$ in a natural way: if $({e}_{1},\mathrm{\dots},{e}_{n})$ is a path $p$ and each edge ${e}_{i}$ is labeled ${a}_{i}$, then the label of $p$ is ${a}_{1}\mathrm{\cdots}{a}_{n}$. Thus, the labels of paths of ${G}_{A}$ are just elements of the monoid ${\mathrm{\Sigma}}^{*}$. The concept^{} can be readily generalized to arbitrary monoids.

Definition. Let $M$ be a monoid. A *semiautomaton* over $M$ is a directed graph $G$ whose edges are labeled by elements of $M$. An *automaton* over $M$ is a semiautomaton over $M$, where the vertex set has two designated subsets $I$ and $F$ (not necessarily disjoint), where elements of $I$ are called the start nodes, and elements of $F$ the final nodes.

Note that if $M={\mathrm{\Sigma}}^{*}$ for some alphabet $\mathrm{\Sigma}$, then a semiautomaton $G$ over $M$ according to the definition given above is not necessarily a semiautomaton over $\mathrm{\Sigma}$ under the standard definition of a semiautomaton, since labels of the edges are words over $\mathrm{\Sigma}$, not elements of $\mathrm{\Sigma}$. However, $G$ can be “transformed” into a “standard” semiautomaton (over $\mathrm{\Sigma}$).

Definition. Let $A$ be a finite automaton over a monoid $M$. An element in $M$ is said to be *accepted by* $A$ if it is the label of a path that begins at an initial node and end at a final node. The set of all elements of $M$ accepted by $A$ is denoted by $L(A)$.

The following is a generalization^{} of Kleene’s theorem^{}.

###### Theorem 1.

. A subset $R$ of a monoid $M$ is a rational set iff $R\mathrm{=}L\mathit{}\mathrm{(}A\mathrm{)}$ for some finite automaton $A$ over $M$.

## References

Title | automaton over a monoid |
---|---|

Canonical name | AutomatonOverAMonoid |

Date of creation | 2013-03-22 19:01:31 |

Last modified on | 2013-03-22 19:01:31 |

Owner | CWoo (3771) |

Last modified by | CWoo (3771) |

Numerical id | 7 |

Author | CWoo (3771) |

Entry type | Definition |

Classification | msc 20M35 |

Classification | msc 68Q70 |