Free monoid

The monoid (N₀,+) 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[4] and the empty sequence to zero establishes an isomorphism from the set of such sequences to N₀. 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.

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 monoid homomorphism from A^∗ to (N₀,+) that maps each element of A to 1. A free monoid is thus a graded 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 of semigroups and that of 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.[6]

For the case of concurrent computation, that is, systems with locks, mutexes or thread joins, the computation can be described with history monoids and trace 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).

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 graded (in the strong sense that only the identity has gradation 0) and equidivisible.[9]

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.[3] A set X of words in A^∗ is a prefix, or has the prefix property, if it does not contain a proper (string) prefix of any of its elements. Every prefix in A⁺ is a code, indeed a prefix code.[3][13]

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]

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]

The computational embodiment of a monoid morphism is a map followed by a fold. In this setting, the free monoid on a set A corresponds to lists of elements from A with concatenation as the binary operation. A monoid homomorphism from the free monoid to any other monoid (M,•) is a function f such that

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

where e is the identity on M. Computationally, every such homomorphism corresponds to a map operation applying f to all the elements of a list, followed by a fold operation which combines the results using the binary operator •. This computational paradigm (which can be generalized to non-associative binary operators) has inspired the MapReduce software framework.

The operation of string projection is an endomorphism. That is, given a letter a ∈ Σ and a string s ∈ Σ^∗, the string projection p_a(s) removes every occurrence of a from s; it is formally defined by

${\displaystyle p_{a}(s)={\begin{cases}\varepsilon &{\text{if }}s=\varepsilon ,{\text{ the empty string}}\\p_{a}(t)&{\text{if }}s=ta\\p_{a}(t)b&{\text{if }}s=tb{\text{ and }}b\neq 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

${\displaystyle p_{a}\left(\Sigma ^{*}\right)=\left(\Sigma -a\right)^{*}}$

where ${\displaystyle p_{a}\left(\Sigma ^{*}\right)}$ 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 ${\displaystyle 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.

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

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 is idempotent, as

${\displaystyle 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.