automaton over a monoid


Recall that a semiautomaton A can be visually represented by a directed graphMathworldPlanetmath GA, whose vertices (or nodes) are states of A, and whose edges are labeled by elements from the input alphabet Σ of A. Labeling can be extended to paths of GA in a natural way: if (e1,,en) is a path p and each edge ei is labeled ai, then the label of p is a1an. Thus, the labels of paths of GA are just elements of the monoid Σ*. The conceptMathworldPlanetmath 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=Σ* for some alphabet Σ, then a semiautomaton G over M 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, G can be “transformed” into a “standard” semiautomaton (over Σ).

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 generalizationPlanetmathPlanetmath of Kleene’s theoremMathworldPlanetmath.

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