Free monoid

The free monoid ${\Sigma }^{\ast }$ on an alphabet $\Sigma$ consists of all finite words over an alphabet, including the empty word $\epsilon$, with concatenation as its binary operation. Distinct strings represent distinct elements: there are no imposed equalities between different sequences of letters. The empty word is its identity element, and concatenation has the associative property.^[ref]

For $\Sigma =\{a,b\}$, the elements begin $\epsilon ,a,b,aa,ab,ba,bb,\dots$. Both $(ab)a$ and $a(ba)$ give the same word $aba$, but $ab\ne ba$, so this monoid is not commutative. The length of a word over an alphabet obeys $\ell (uv)=\ell (u)+\ell (v)$; it is a monoid homomorphism to the nonnegative integers with addition. A nonempty word has no inverse element, since joining it to any other word cannot decrease its length to zero.

The defining benefit of being free is that letters can stand for arbitrary elements of another monoid. Choose a value $h(a)$ for each letter $a\in \Sigma$; then $h(a_1\cdots a_n)=h(a_1)\ast \cdots \ast h(a_n)$, with $h(\epsilon )=e$, is the unique monoid homomorphism extending those choices. Associativity and the identity element make this evaluation consistent for every finite word. For example, interpreting the letters as self-maps evaluates a word as a composed transformation; interpreting them as nonnegative counts evaluates it by addition.