Free monoid

Free monoid

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"+.

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.

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.

tring projection

The operation of ml|String_operations|String_projection|string projection is an endomorphism. That is, given a letter "a" ∈ Σ and a string "s" ∈ Σ∗, define the string projection "p"a("s") by

:p_a(s) = egin{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 e 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_aleft(Sigma^* ight)= left(Sigma-a ight)^*

where p_aleft(Sigma^* ight) 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 p_a(st)=p_a(s)p_a(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

:p_a(p_b(s))=p_b(p_a(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

:p_a(p_a(s))=p_a(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". This forms a commutative monoid with the binary operation of multiset union.

For example, if "A" = {"a", "b", "c"} elements of the free commutative monoid on "A" are of the form:{ε, "a", "ab", "a"2"b", "ab"3"c"4}

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.

ee also

* String operations


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Monoid — This article is about the mathematical concept. For the alien creatures in the Doctor Who adventure, see The Ark (Doctor Who). Coherence law for monoid unit In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a… …   Wikipedia

  • Free object — In mathematics, the idea of a free object is one of the basic concepts of abstract algebra. It is a part of universal algebra, in the sense that it relates to all types of algebraic structure (with finitary operations). It also has a clean… …   Wikipedia

  • Free algebra — This article is about free algebras in ring theory. For the more general free algebras in universal algebra, see free object. In mathematics, especially in the area of abstract algebra known as ring theory, a free algebra is the noncommutative… …   Wikipedia

  • Monoid ring — In abstract algebra, a monoid ring is a new ring constructed from some other ring and a monoid. Definition Let R be a ring and G be a monoid. Consider all the functions φ  : G → R such that the set {g: φ(g) ≠ 0} is finite. Let all such… …   Wikipedia

  • Free group — In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses (disregarding trivial variations such as st 1 =… …   Wikipedia

  • Presentation of a monoid — In algebra, a presentation of a monoid (or semigroup) is a description of a monoid (or semigroup) in terms of a set Sigma; of generators and a set of relations on the free monoid Sigma; lowast; (or free semigroup Sigma;+) generated by Sigma;. The …   Wikipedia

  • History monoid — In mathematics and computer science, a history monoid is a way of representing the histories of concurrently running computer processes as a collection of strings, each string representing the individual history of a process. The history monoid… …   Wikipedia

  • Trace monoid — In mathematics and computer science, a trace is a set of strings, wherein certain letters in the string are allowed to commute, but others are not. It generalizes the concept of a string, by not forcing the letters to always be in a fixed order,… …   Wikipedia

  • Refinement monoid — In mathematics, a refinement monoid is a commutative monoid M such that for any elements a0, a1, b0, b1 of M such that a0+a1=b0+b1, there are elements c00, c01, c10, c11 of M such that a0=c00+c01, a1=c10+c11, b0=c00+c10, and b1=c01+c11. A… …   Wikipedia

  • Aperiodic monoid — In mathematics, an aperiodic semigroup is a semigroup S such that for every x ∈ S , there exists a nonnegative integer n such that xn = xn + 1 .An aperiodic monoid is an aperiodic semigroup which is a monoid. This notion is in some sense… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”