I am reading Berstel's and Perrin's THEORY OF CODES.
Now I have trouble understanding the concept of a (non)free monoid.
Given any set $A$ equipping this set with concatention and the empty word I can make a monoid out of it called the free monoid, denoted by $A^*$.
This definition is pretty straightforward, then given any monoid $M$, $M$ is free is there is a isomorphism between $M$ and a free monoid.
What I don't understand is that since any monoid has a (unique and minimal) set of generators $X$, i.e. $X^*=M$, why is it not always the case that $M$ is free.
It can be proved that a monoid is free if it's minimal set of generators is a code.
Here are two examples of monoids over $A = \{a,b\}$.
- $M = \{w \in A^* : |w|_a \equiv 0 \text{ mod } 2 \}$
- $N = X^*$, where $X = \{ a, ba, ab\}$
The minimal set of generators of the first example is a code, thus $M$ is free and the minimal set of generators of $N$ is not a code, thus $N$ is not free, but I don't see how $N$ is not free, if $X$ is a set and we take every possible string made out of elements of x and on the other hand why is $M$ free could someone give a isomorphism to a free monoid.
Thanks.
A monoid $M$ is freely generated by $X$ if every element of $M$ can be uniquely written as a product of generators from $X$. In your second example $\{a,ba,ab\}$ does not freely generate $N$. For example, the word $abaaba$ can be written in two ways: $ab\cdot a\cdot a\cdot ba=a\cdot ba\cdot ab\cdot a$.