Editing Free monoid (section)

== Examples ==

=== Natural numbers ===
The monoid ('''N<sub>0</sub>''',+) of [[natural 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<ref>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.</ref>
and the empty sequence to zero establishes an isomorphism from the set of such sequences to '''N<sub>0</sub>'''.
This isomorphism is compatible with "+", that is, for any two sequences ''s'' and ''t'', if ''s'' is mapped (i.e. evaluated) to a number ''m'' and ''t'' to ''n'', then their concatenation ''s''+''t'' is mapped to the sum ''m''+''n''.

=== Kleene star ===
In [[formal language]] theory, usually a finite set of "symbols" A (sometimes called the [[alphabet (formal languages)|alphabet]]) is considered. A finite sequence of symbols is called a "word over ''A''", and the free monoid ''A''<sup>&lowast;</sup> 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''<sup>&lowast;</sup> contains all concatenations of ''a'', ''b'', and ''c'':
:{ε, ''a'', ''ab'', ''ba'', ''caa'', ''{{not a typo|cccbabbc}}'', ...}.

If ''A'' is any set, the ''word length'' function on ''A''<sup>&lowast;</sup> is the unique [[monoid homomorphism]] from ''A''<sup>&lowast;</sup> to ('''N<sub>0</sub>''',+) that maps each element of ''A'' to 1.  A free monoid is thus a '''graded monoid'''.<ref name=Sak382>Sakarovitch (2009) p.382</ref> (A graded monoid <math>M</math> is a monoid that can be written as <math>M=M_0\oplus M_1\oplus M_2 \cdots</math>. Each <math>M_n</math> is a grade; the grading here is just the length of the string. That is, <math>M_n</math> contains those strings of length <math>n.</math> The <math>\oplus</math> symbol here can be taken to mean "set union"; it is used instead of the symbol <math>\cup</math> because, in general, set unions might not be monoids, and so a distinct symbol is used. By convention, gradations are always written with the <math>\oplus</math> symbol.)

There are deep connections between the theory of [[semigroup]]s and that of [[automata theory|automata]]. For example, every formal language has a [[syntactic monoid]] that recognizes that language. For the case of a [[regular language]], that monoid is isomorphic to the [[transition monoid]] associated to the [[semiautomaton]] of some [[deterministic 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.<ref>
{{Cite book|url=https://books.google.com/books?id=C5QbCAAAQBAJ|title=Groups, Languages, Algorithms: AMS-ASL Joint Special Session on Interactions Between Logic, Group Theory, and Computer Science, January 16-19, 2003, Baltimore, Maryland|last=Borovik|first=Alexandre|date=2005-01-01|publisher=American Mathematical Soc.|isbn=9780821836187|language=en}}
</ref> 

For the case of [[concurrent computation]], that is, systems with [[lock (computer science)|locks]], [[mutex]]es or [[thread join]]s, the computation can be described with [[history monoid]]s and [[trace monoid]]s. 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).