automaton over a monoid
Recall that a semiautomaton can be visually represented by a directed graph , whose vertices (or nodes) are states of , and whose edges are labeled by elements from the input alphabet of . Labeling can be extended to paths of in a natural way: if is a path and each edge is labeled , then the label of is . Thus, the labels of paths of are just elements of the monoid . The concept can be readily generalized to arbitrary monoids.
Definition. Let be a monoid. A semiautomaton over is a directed graph whose edges are labeled by elements of . An automaton over is a semiautomaton over , where the vertex set has two designated subsets and (not necessarily disjoint), where elements of are called the start nodes, and elements of the final nodes.
Note that if for some alphabet , then a semiautomaton over according to the definition given above is not necessarily a semiautomaton over under the standard definition of a semiautomaton, since labels of the edges are words over , not elements of . However, can be “transformed” into a “standard” semiautomaton (over ).
Definition. Let be a finite automaton over a monoid . An element in is said to be accepted by 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 accepted by is denoted by .
. A subset of a monoid is a rational set iff for some finite automaton over .