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