automaton over a monoid
Recall that a semiautomaton A can be visually represented by a directed graph 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 a1⋯an. Thus, the labels of paths of GA are just elements of the monoid Σ*. 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=Σ* 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 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 |
---|---|
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 |