Inabstract algebra, thefree monoid on aset is themonoid whose elements are all thefinite sequences (or strings) of zero or more elements from that set, withstring concatenation as the monoid operation and with the unique sequence of zero elements, often called theempty string and denoted by ε or λ, as theidentity element. The free monoid on a setA is usually denotedA^∗. Thefree semigroup onA is the subsemigroup ofA^∗ containing all elements except the empty string. It is usually denotedA⁺.^[1][2]

More generally, an abstract monoid (or semigroup)S is described asfree if it isisomorphic to the free monoid (or semigroup) on some set.^[3]

As the name implies, free monoids and semigroups are those objects which satisfy the usualuniversal property definingfree objects, in the respectivecategories 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) areassociative, by definition; that is, they are written without any parenthesis to show grouping or order of operation. The non-associative equivalent is thefree magma.

The monoid (N₀,+) ofnatural numbers (including zero) under addition is a free monoid on a singleton free generator, in this case, the natural number 1. According to the formal definition, this monoid consists of all sequences like "1", "1+1", "1+1+1", "1+1+1+1", and so on, including the empty sequence. Mapping each such sequence to its evaluation result^[4]and the empty sequence to zero establishes an isomorphism from the set of such sequences toN₀.This isomorphism is compatible with "+", that is, for any two sequencess andt, ifs is mapped (i.e. evaluated) to a numberm andt ton, then their concatenations+t is mapped to the summ+n.

The free monoid over the setN₀ of natural numbers is (T,⟨⟩,::), whereT denotes the set oftuples of natural numbers,⟨⟩ denotes the unique 0-tuple, and :: denotes tuple concatenation. The monoids (N₀,+) and (T,⟨⟩,::) are not isomorphic, since + happens to be commutative, while :: is not.

Informal language theory, usually a finite set of "symbols" A (sometimes called thealphabet) is considered. A finite sequence of symbols is called a "word overA", and the free monoidA^∗ is called the "Kleene star ofA".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 alphabetA = {a,b,c}, its Kleene starA^∗ contains all concatenations ofa,b, andc:

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

IfA is any set, theword length function onA^∗ is the uniquemonoid homomorphism fromA^∗ to (N₀,+) that maps each element ofA to 1. A free monoid is thus agraded monoid.^[5] (A graded monoid${\displaystyle M}$ is a monoid that can be written as${\displaystyle M=M_0\oplus M_1\oplus M_2\cdots }$. Each${\displaystyle M_n}$ is a grade; the grading here is just the length of the string. That is,${\displaystyle M_n}$ contains those strings of length${\displaystyle n.}$ The${\displaystyle \oplus }$ symbol here can be taken to mean "set union"; it is used instead of the symbol${\displaystyle \cup }$ because, in general, set unions might not be monoids, and so a distinct symbol is used. By convention, gradations are always written with the${\displaystyle \oplus }$ symbol.)

There are deep connections between the theory ofsemigroups and that ofautomata. For example, every formal language has asyntactic monoid that recognizes that language. For the case of aregular language, that monoid is isomorphic to thetransition monoid associated to thesemiautomaton of somedeterministic finite automaton that recognizes that language. The regular languages over an alphabet A are the closure of the finite subsets of A*, the free monoid over A, under union, product, and generation of submonoid.^[6]

For the case ofconcurrent computation, that is, systems withlocks,mutexes orthread joins, the computation can be described withhistory monoids andtrace monoids. Roughly speaking, elements of the monoid can commute, (e.g. different threads can execute in any order), but only up to a lock or mutex, which prevent further commutation (e.g. serialize thread access to some object).

We define a pair of words inA^∗ of the formuv andvu asconjugate: the conjugates of a word are thus itscircular shifts.^[7] Two words are conjugate in this sense if they areconjugate in the sense of group theory as elements of thefree group generated byA.^[8]

A free monoid isequidivisible: if the equationmn =pq holds, then there exists ans such that eitherm =ps,sn =q (example see image) orms =p,n =sq.^[9] This result is also known asLevi's lemma.^[10]

A monoid is free if and only if it isgraded (in the strong sense that only the identity has gradation 0) and equidivisible.^[9]

The members of a setA are called thefree generators forA^∗ andA⁺. The superscript * is then commonly understood to be theKleene star. More generally, ifS 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 monoidA^∗ (semigroupA⁺) is called aset of free generators forS.

Each free monoid (or semigroup)S has exactly one set of free generators, thecardinality of which is called therank ofS.

Two free monoids or semigroups are isomorphic if and only if they have the same rank. In fact,everyset of generators for a free monoid or semigroupS 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.

AsubmonoidN ofA^∗ isstable ifu,v,ux,xv inN together implyx inN.^[11] A submonoid ofA^∗ is stable if and only if it is free.^[12]For example, using the set ofbits { "0", "1" } asA, the setN of all bit strings containing an even number of "1"s is a stable submonoid because ifu contains an even number of "1"s, andux as well, thenx must contain an even number of "1"s, too. WhileN cannot be freely generated by any set of single bits, itcan be freely generated by the set of bit strings { "0", "11", "101", "1001", "10001", ... } – the set of strings of the form "10ⁿ1" for some nonnegative integern (along with the string "0").

A set of free generators for a free monoidP is referred to as abasis forP: a set of wordsC is acode ifC* is a free monoid andC is a basis.^[3] A setX of words inA^∗ is aprefix, or has theprefix property, if it does not contain a proper(string) prefix of any of its elements. Every prefix inA⁺ is a code, indeed aprefix code.^[3][13]

A submonoidN ofA^∗ isright unitary ifx,xy inN impliesy inN. A submonoid is generated by a prefix if and only if it is right unitary.^[14]

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. TheChen–Fox–Lyndon theorem states that theLyndon words furnish a factorization. More generally,Hall words provide a factorization; the Lyndon words are a special case of the Hall words.

The intersection of free submonoids of a free monoidA^∗ is again free.^[15][16] IfS is a subset of a free monoidA* then the intersection of all free submonoids ofA* containingS is well-defined, sinceA* itself is free, and containsS; it is a free monoid and called thefree hull ofS. A basis for this intersection is a code.

Thedefect theorem^[15][16][17] states that ifX is finite andC is the basis of the free hull ofX, then eitherX is a code andC =X, or

|C| ≤ |X| − 1 .

Amonoid morphismf from a free monoidB^∗ to a monoidM is a map such thatf(xy) =f(x)⋅f(y) for wordsx,y andf(ε) = ι, where ε and ι denote the identity elements ofB^∗ andM, respectively. The morphismf is determined by its values on the letters ofB and conversely any map fromB toM extends to a morphism. A morphism isnon-erasing^[18] orcontinuous^[19] if no letter ofB maps to ι andtrivial if every letter ofB maps to ι.^[20]

A morphismf from a free monoidB^∗ to a free monoidA^∗ istotal if every letter ofA occurs in some word in the image off;cyclic^[20] orperiodic^[21] if the image off is contained in {w}^∗ for some wordw ofA^∗. A morphismf isk-uniform if the length |f(a)| is constant and equal tok for alla inA.^[22][23] A 1-uniform morphism isstrictly alphabetic^[19] or acoding.^[24]

A morphismf from a free monoidB^∗ to a free monoidA^∗ issimplifiable if there is an alphabetC of cardinality less than that ofB such the morphismf factors throughC^∗, that is, it is the composition of a morphism fromB^∗ toC^∗ and a morphism from that toA^∗; otherwisef iselementary. The morphismf is called acode if the image of the alphabetB underf is a code. Every elementary morphism is a code.^[25]

ForL a subset ofB^∗, a finite subsetT ofL is atest set forL if morphismsf andg onB^∗ agree onL if and only if they agree onT. TheEhrenfeucht conjecture is that any subsetL has a test set:^[26] it has been proved^[27] independently by Albert and Lawrence; McNaughton; and Guba. The proofs rely onHilbert's basis theorem.^[28]

This sectiondoes notcite anysources. Please helpimprove this section byadding citations to reliable sources. Unsourced material may be challenged andremoved.(February 2015) (Learn how and when to remove this message)

The computational embodiment of a monoid morphism is amap followed by afold.^[29] In this setting, the free monoid on a setA corresponds tolists of elements fromA with concatenation as the binary operation. A monoid homomorphism from the free monoid to any other monoid (M,•) is a functionf such that

• f(x₁...x_n) =f(x₁) • ... •f(x_n)
• f() =e

wheree is the identity onM. Computationally, every such homomorphism corresponds to amap operation applyingf to all the elements of a list, followed by afold operation which combines the results using the binary operator •. Thiscomputational paradigm (which can be generalized to non-associative binary operators) has inspired theMapReduce software framework.^[30]

Anendomorphism ofA^∗ is a morphism fromA^∗ to itself.^[31] Theidentity mapI is an endomorphism ofA^∗, and the endomorphisms form amonoid undercomposition of functions.

An endomorphismf isprolongable if there is a lettera such thatf(a) =as for a non-empty strings.^[32]

The operation ofstring projection is an endomorphism. That is, given a lettera ∈ Σ and a strings ∈ Σ^∗, the string projectionp_a(s) removes every occurrence ofa froms; 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 amorphism in the category of free monoids, so that

${\displaystyle p_a\left({\mathrm{\Sigma }}^{\ast }\right)={\left(\mathrm{\Sigma }-a\right)}^{\ast }}$

where${\displaystyle p_a\left({\mathrm{\Sigma }}^{\ast }\right)}$ is understood to be the free monoid of all finite strings that don't contain the lettera. Projection commutes with the operation of string concatenation, so that${\displaystyle p_a(st)=p_a(s)p_a(t)}$ for all stringss andt. There are many right inverses to string projection, and thus it is asplit epimorphism.

The identity morphism is${\displaystyle p_{\epsilon },}$ defined as${\displaystyle p_{\epsilon }(s)=s}$ for all stringss, and${\displaystyle p_{\epsilon }(\epsilon )=\epsilon }$.

String projection is commutative, as clearly

${\displaystyle 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 isidempotent, as

${\displaystyle p_a(p_a(s))=p_a(s)}$

for all stringss. Thus, projection is an idempotent, commutative operation, and so it forms a boundedsemilattice or a commutativeband.

Given a setA, thefreecommutative monoid onA is the set of all finitemultisets with elements drawn fromA, with the monoid operation being multiset sum and the monoid unit being the empty multiset.

For example, ifA = {a,b,c}, elements of the free commutative monoid onA are of the form

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

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

Thefree commutative semigroup is the subset of the free commutative monoid that contains all multisets with elements drawn fromA except the empty multiset.

Thefree partially commutative monoid, ortrace monoid, is a generalization that encompasses both the free and free commutative monoids as instances. This generalization finds applications incombinatorics and in the study ofparallelism incomputer science.

• String operations

• Allouche, Jean-Paul;Shallit, Jeffrey (2003),Automatic Sequences: Theory, Applications, Generalizations,Cambridge University Press,ISBN 978-0-521-82332-6,Zbl 1086.11015
• Berstel, Jean;Perrin, Dominique; Reutenauer, Christophe (2010),Codes and automata, Encyclopedia of Mathematics and its Applications, vol. 129, Cambridge:Cambridge University Press,ISBN 978-0-521-88831-8,Zbl 1187.94001
• Lothaire, M. (1997),Combinatorics on words, Cambridge Mathematical Library, vol. 17, Contributors: Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, J. E.; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, M. P.; Choffrut, C.; Cori, R. Series editors: Lyndon, Roger; Rota, Gian-Carlo. Foreword by Roger Lyndon (2nd ed.),Cambridge University Press,doi:10.1017/CBO9780511566097,ISBN 0-521-59924-5,MR 1475463,Zbl 0874.20040
• Lothaire, M. (2011),Algebraic combinatorics on words, Encyclopedia of Mathematics and Its Applications, vol. 90, With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.),Cambridge University Press,ISBN 978-0-521-18071-9,Zbl 1221.68183
• Lothaire, M. (2005),Applied combinatorics on words, Encyclopedia of Mathematics and Its Applications, vol. 105, A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot,Gesine Reinert,Sophie Schbath, Michael Waterman, Philippe Jacquet,Wojciech Szpankowski, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche andValérie Berthé, Cambridge:Cambridge University Press,ISBN 0-521-84802-4,Zbl 1133.68067
• Pytheas Fogg, N. (2002),Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. (eds.),Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Mathematics, vol. 1794, Berlin:Springer-Verlag,ISBN 3-540-44141-7,Zbl 1014.11015
• Sakarovitch, Jacques (2009),Elements of automata theory, Translated from the French by Reuben Thomas, Cambridge:Cambridge University Press,ISBN 978-0-521-84425-3,Zbl 1188.68177
• Salomaa, Arto (1981),Jewels of Formal Language Theory, Pitman Publishing,ISBN 0-273-08522-0,Zbl 0487.68064

• Semigroup theory
• Formal languages
• Free algebraic structures
• Combinatorics on words

• CS1 maint: work parameter with ISBN
• Articles with short description
• Short description matches Wikidata
• Articles needing additional references from February 2015
• All articles needing additional references