## You are here

Homeautomaton over a monoid

## Primary tabs

# 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

- 1 S. Eilenberg, Automata, Languages, and Machines, Vol. A, Academic Press (1974).

## Mathematics Subject Classification

20M35*no label found*68Q70

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections