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*. The identity element is the unique sequence of zero letters, often called the empty string and denoted by ε or λ. The free semigroup on A is the subsemigroup of A* containing all elements except the empty string. It is usually denoted A⁺. Abstract algebra is the field of mathematics concerned with the study of algebraic structures such as groups, rings and fields. ... In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single, associative binary operation and an identity element. ... In various branches of mathematics and computer science, strings are sequences of various simple objects (symbols, tokens, characters, etc. ... In mathematics, a binary operation, or binary operator, is a calculation involving two input quantities and one kind of a specific operation. ... In formal language theory (and therefore in programming languages), concatenation is the operation of joining two character strings end to end. ... In mathematics, an identity element (or neutral element) is a special type of element of a set with respect to a binary operation on that set. ... In various branches of mathematics and computer science, strings are sequences of various simple objects (symbols, tokens, characters, etc. ... In mathematics, a semigroup is an algebraic structure consisting of a set S closed under an associative binary operation. ...

More generally, an abstract monoid (or semigroup) S is described as free if it is isomorphic to the free monoid (or semigroup) on some set. In mathematics, an isomorphism (in Greek isos = equal and morphe = shape) is a kind of interesting mapping between objects. ...

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. In various branches of mathematics, certain constructions are frequently defined or characterised by an abstract property which requires the existence of a unique morphism under certain conditions. ... The idea of a free object in mathematics is one of the basics of abstract algebra. ... In mathematics, categories allow one to formalize notions involving abstract structure and processes which preserve structure. ...

Free generators and rank

The members of a set A are called the free generators for A* and A⁺. More generally, if S is an abstract free monoid (semigroup), then a set of elements which maps onto the set of single-letter words under an isomorphism to a semigroup A⁺ (monoid A*) is called a set of free generators for S.

Each free semigroup (or monoid) S has exactly one set of free generators, the cardinality of which is called the rank of S. In mathematics, the cardinality of a set is a measure of the number of elements of the set. There are two approaches to cardinality – one which compares sets directly using bijections, injections, and surjections, and another which uses cardinal numbers. ...

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. Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is...

If Σ is a finite alphabet (a set of symbols), then Σ* consists of all words over Σ in the sense of formal language theory. Thus, the abstract study of formal languages can be thought of as the study of subsets of finitely generated free monoids. There are deep connections between the theory of semigroups and that of automata. For example, the regular languages over Σ are the homomorphic pre-images in Σ* of subsets of finite monoids. In mathematics, logic, and computer science, a formal language is a set of finite-length words (i. ... In theoretical computer science, automata theory is the study of abstract machines and problems they are able to solve. ... A regular language is a formal language (i. ...

For example, if A = {a, b, c} elements of A* are of the form

{ε, a, ab, ba, caa, cccbabbc}

If A is a set, the word length function on A* is the unique monoid homomorphism from A* to N that maps each element of A to 1. In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single, associative binary operation and an identity element. ...

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. In mathematics, a multiset (sometimes also called a bag) differs from a set in that each member has a multiplicity, which is a natural number indicating (loosely speaking) how many times it is a member, or perhaps how many memberships it has in the multiset. ... In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single, associative binary operation and an identity element. ...

For example, if A = {a, b, c} elements of the free commutative monoid on A are of the form

{ε, a, ab, a²b, ab³c⁴}

See also

• Kleene star