free submonoid

Let $A$ be an arbitrary set,let $A^{\ast }$ be the free monoid on $A$,and let $e$ be the identity element (empty word) of $A^{\ast }$.

Let $M$ be a submonoid of $A^{\ast }$.The minimal generating set of $M$ is

$$\mathrm{mgs}(M)=(M\setminus \{e\})\setminus {(M\setminus \{e\})}^2.$$(1)

Shortly, $\mathrm{mgs}(M)$ is the set of all the nontrivial elements of $M$that cannot be “reconstructed” as products of elements of $M$.It is straightforward that

1. ${(\mathrm{mgs}(M))}^{\ast }=M$, and

2. if $S\subseteq A^{\ast }$ and $M\subseteq S^{\ast }$,then $\mathrm{mgs}(M)\subseteq S$.

We say that $M$ is a free submonoid of $A^{\ast }$if it is isomorphic (as a monoid)to a free monoid $B^{\ast }$ for some set $B$.A set $K\subseteq A^{\ast }$ such that $K=\mathrm{mgs}(M)$for some free submonoid $M$ of $A^{\ast }$is also called a code.