The Full Wiki

Free semigroup: Wikis

Advertisements

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

(Redirected to Free monoid article)

From Wikipedia, the free encyclopedia

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. It is usually denoted A. The identity element is the unique sequence of zero elements, often called the empty string and denoted by ε or λ, and the monoid operation is string concatenation. The free semigroup on A is the subsemigroup of A containing all elements except the empty string. It is usually denoted A+.

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.

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.

Contents

Free generators and rank

The members of a set A are called the free generators for A and A+. The superscript * is then commonly understood to be the Kleene star. 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.

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

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.

String projection

The operation of string projection is an endomorphism. That is, given a letter a ∈ Σ and a string s ∈ Σ, define the string projection pa(s) by

p_a(s) = \begin{cases} \varepsilon & \mbox{if } s=\varepsilon \mbox{ the empty string} \ p_a(t) & \mbox{if } s=ta \\ p_a(t)b & \mbox{if } s=tb \mbox{ and } b\ne a \end{cases}

Note that string projection is well-defined even if the rank of the monoid is infinite, as the above recursive definition works for all strings of finite length. String projection is a morphism in the category of free monoids, so that

p_a\left(\Sigma^*\right)= \left(\Sigma-a\right)^*

where p_a\left(\Sigma^*\right) is understood to be the free monoid of all finite strings that don't contain the letter a. The identity morphism is p_\varepsilon, as clearly p_\varepsilon(s)=s for all strings s. Of course, it commutes with the operation of string concatenation, so that pa(st) = pa(s)pa( t) for all strings s and t. There are many right inverses to string projection, and thus it is a split epimorphism.

String projection is commutative, as clearly

pa(pb( s)) = pb(pa( s))

For free monoids of finite rank, this follows from the fact that free monoids of the same rank are isomorphic, as projection reduces the rank of the monoid by one.

String projection is idempotent, as

pa(pa( s)) = pa(s)

for all strings s. Thus, projection is an idempotent, commutative operation, and so it forms a bounded semilattice or a commutative band.

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, with the monoid operation being multiset union and the monoid unit being the empty multiset.

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

{ε, a, ab, a2b, ab3c4}

The fundamental theorem of arithmetic states that the monoid of positive integers under multiplication is a free commutative monoid on an infinite set of generators, the prime numbers.

The free commutative semigroup is the subset of the free commutative monoid which contains all multisets with elements drawn from A except the empty multiset.

Generalization

The free partially commutative monoid, or trace monoid, is a generalization that encompasses both the free and free commutative monoids as instances. This generalization finds applications in combinatorics and in the study of parallelism in computer science.

See also

Advertisements

Advertisements






Got something to say? Make a comment.
Your name
Your email address
Message