# 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 $\Sigma$ of $A$. Labeling can be extended to paths of $G_{A}$ in a natural way: if $(e_{1},\ldots,e_{n})$ is a path $p$ and each edge $e_{i}$ is labeled $a_{i}$, then the label of $p$ is $a_{1}\cdots a_{n}$. Thus, the labels of paths of $G_{A}$ are just elements of the monoid $\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=\Sigma^{*}$ for some alphabet $\Sigma$, then a semiautomaton $G$ over $M$ according to the definition given above is not necessarily a semiautomaton over $\Sigma$ under the standard definition of a semiautomaton, since labels of the edges are words over $\Sigma$, not elements of $\Sigma$. However, $G$ can be “transformed” into a “standard” semiautomaton (over $\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=L(A)$ for some finite automaton $A$ over $M$.

## References

Title automaton over a monoid AutomatonOverAMonoid 2013-03-22 19:01:31 2013-03-22 19:01:31 CWoo (3771) CWoo (3771) 7 CWoo (3771) Definition msc 20M35 msc 68Q70