Free monoid
In
More generally, an abstract monoid (or semigroup) S is described as free if it is
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 monoids (and monoids in general) are
Examples
Natural numbers
The monoid (N0,+) of
Kleene star
In formal language theory, usually a finite set of "symbols" A (sometimes called the alphabet) is considered. A finite sequence of symbols is called a "word over A", and the free monoid A∗ is called the "Kleene star of A". Thus, the abstract study of formal languages can be thought of as the study of subsets of finitely generated free monoids.
For example, assuming an alphabet A = {a, b, c}, its Kleene star A∗ contains all concatenations of a, b, and c:
- {ε, a, ab, ba, caa, cccbabbc, ...}.
If A is any set, the word length function on A∗ is the unique
There are deep connections between the theory of
For the case of
Conjugate words
We define a pair of words in A∗ of the form uv and vu as conjugate: the conjugates of a word are thus its
Equidivisibility
A free monoid is equidivisible: if the equation mn = pq holds, then there exists an s such that either m = ps, sn = q (example see image) or ms = p, n = sq.[9] This result is also known as Levi's lemma.[10]
A monoid is free if and only if it is
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 monoid A∗ (semigroup A+) is called a set of free generators for S.
Each free monoid (or semigroup) 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 monoid or semigroup S contains the free generators, since a free generator has word length 1 and hence can only be generated by itself. It follows that a free semigroup or monoid is finitely generated if and only if it has finite rank.
A
Codes
A set of free generators for a free monoid P is referred to as a basis for P: a set of words C is a code if C* is a free monoid and C is a basis.
A submonoid N of A∗ is right unitary if x, xy in N implies y in N. A submonoid is generated by a prefix if and only if it is right unitary.[14]
Factorization
A factorization of a free monoid is a sequence of subsets of words with the property that every word in the free monoid can be written as a concatenation of elements drawn from the subsets. The
Free hull
The intersection of free submonoids of a free monoid A∗ is again free.[15][16] If S is a subset of a free monoid A* then the intersection of all free submonoids of A* containing S is well-defined, since A* itself is free, and contains S; it is a free monoid and called the free hull of S. A basis for this intersection is a code.
The defect theorem[15][16][17] states that if X is finite and C is the basis of the free hull of X, then either X is a code and C = X, or
- |C| ≤ |X| − 1 .
Morphisms
A
A morphism f from a free monoid B∗ to a free monoid A∗ is total if every letter of A occurs in some word in the image of f; cyclic[20] or periodic[21] if the image of f is contained in {w}∗ for some word w of A∗. A morphism f is k-uniform if the length |f(a)| is constant and equal to k for all a in A.[22][23] A 1-uniform morphism is strictly alphabetic[19] or a coding.[24]
A morphism f from a free monoid B∗ to a free monoid A∗ is simplifiable if there is an alphabet C of cardinality less than that of B such the morphism f factors through C∗, that is, it is the composition of a morphism from B∗ to C∗ and a morphism from that to A∗; otherwise f is elementary. The morphism f is called a code if the image of the alphabet B under f is a code. Every elementary morphism is a code.[25]
Test sets
For L a subset of B∗, a finite subset T of L is a test set for L if morphisms f and g on B∗ agree on L if and only if they agree on T. The Ehrenfeucht conjecture is that any subset L has a test set:[26] it has been proved[27] independently by Albert and Lawrence; McNaughton; and Guba. The proofs rely on Hilbert's basis theorem.[28]
Map and fold
The computational embodiment of a monoid morphism is a
- f(x1...xn) = f(x1) • ... • f(xn)
- f() = e
where e is the identity on M. Computationally, every such homomorphism corresponds to a
Endomorphisms
An
An endomorphism f is prolongable if there is a letter a such that f(a) = as for a non-empty string s.[30]
String projection
The operation of string projection is an endomorphism. That is, given a letter a ∈ Σ and a string s ∈ Σ∗, the string projection pa(s) removes every occurrence of a from s; it is formally defined by
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
where is understood to be the free monoid of all finite strings that don't contain the letter a. Projection commutes with the operation of string concatenation, so that for all strings s and t. There are many right inverses to string projection, and thus it is a
The identity morphism is defined as for all strings s, and .
String projection is commutative, as clearly
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
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
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 that contains all multisets with elements drawn from A except the empty multiset.
The
See also
Notes
- ^ Lothaire (1997, pp. 2–3), [1]
- ^ Pytheas Fogg (2002, p. 2)
- ^ a b c Lothaire (1997, p. 5)
- ^ Since addition of natural numbers is associative, the result doesn't depend on the order of evaluation, thus ensuring the mapping to be well-defined.
- ^ Sakarovitch (2009) p.382
- ^
Borovik, Alexandre (2005-01-01). Groups, Languages, Algorithms: AMS-ASL Joint Special Session on Interactions Between Logic, Group Theory, and Computer Science, January 16-19, 2003, Baltimore, Maryland. American Mathematical Soc. ISBN 9780821836187.
- ^ Sakarovitch (2009) p.27
- ^ Pytheas Fogg (2002, p. 297)
- ^ a b Sakarovitch (2009) p.26
- ISBN 978-3-642-64150-3.
- ^ Berstel, Perrin & Reutenauer (2010, p. 61)
- ^ Berstel, Perrin & Reutenauer (2010, p. 62)
- ^ Berstel, Perrin & Reutenauer (2010, p. 58)
- ^ Lothaire (1997, p. 15)
- ^ a b Lothaire (1997, p. 6)
- ^ a b Lothaire (2011, p. 204)
- ^ Berstel, Perrin & Reutenauer (2010, p. 66)
- ^ Lothaire (1997, p. 7)
- ^ a b Sakarovitch (2009, p. 25)
- ^ a b Lothaire (1997, p. 164)
- ^ Salomaa (1981, p. 77)
- ^ Lothaire (2005, p. 522)
- Zbl 1250.68007.
- ^ Allouche & Shallit (2003, p. 9)
- ^ Salomaa (1981, p. 72)
- ^ Lothaire (1997, pp. 178–179)
- ^ Lothaire (2011, p. 451)
- ^ Salomaa, A. (October 1985). "The Ehrenfeucht conjecture: A proof for language theorists". Bulletin of the EATCS (27): 71–82.
- ^ Lothaire (2011, p. 450)
- ^ Allouche & Shallit (2003) p.10
References
- Allouche, Jean-Paul; Zbl 1086.11015
- Zbl 1187.94001
- Zbl 0874.20040
- Zbl 1221.68183
- Zbl 1133.68067
- Pytheas Fogg, N. (2002), Zbl 1014.11015
- Sakarovitch, Jacques (2009), Elements of automata theory, Translated from the French by Reuben Thomas, Cambridge: Zbl 1188.68177
- Zbl 0487.68064
External links
- Media related to Free monoid at Wikimedia Commons