|
In abstract algebra, the free monoid on a set A is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from A, with the binary operation of concatenation. It is usually denoted A As the name implies, free monoids and semigroups are those objects which satisfy the usual universal property defining free objects, in the respective categories of monoids and semigroups. It follows that every monoid (or semigroup) arises as a homomorphic image of a free monoid (or semigroup). The study of semigroups as images of free semigroups is called combinatorial semigroup theory.
Free generators and rank The members of a set A are called the free generators for A Each free semigroup (or monoid) S has exactly one set of free generators, the cardinality of which is called the rank of S. Two free monoids or semigroups are isomorphic if and only if they have the same rank. In fact, every set of generators for a free semigroup or monoid S contains the free generators. It follows that a free semigroup or monoid is finitely generated if and only if it has finite rank. Examples The monoid (N,+) of natural numbers (including zero) under addition is a free monoid on a single generator (i.e. rank 1). The unique free generator is the number 1. If Σ is a finite alphabet (a set of symbols), then Σ For example, if A = elements of A If A is a set, the word length function on A The free commutative monoid Given a set A, the free commutative monoid on A is the set of all finite multisets with elements drawn from A. This forms a commutative monoid with the binary operation of multiset union. For example, if A = elements of the free commutative monoid on A are of the form See also | ||||||||
|
| |||||||||
 |
|
| |