submonoid of monoid.

296 Views Asked by At

Let $M = \{a,b,c\}^*$ be a free monoid. Let consider $M' = \{abc, abcba, baabc, baba\}^*$ Check, if $M'$ is a free submonoid of $M$

The solution is:

$M'$ is not a free submonoid of $M$ beacuse: $abcbabaabc = abc \cdot baba \cdot abc = abcba \cdot baabc.$

I don't understand why this fact deny that $M'$ is a free submonoid. I know that fact:

If $T \subset S $ and S is a free monoid and $T^2 \subset T$ and $e \in T$ then $T$ is submonoid of S

1

There are 1 best solutions below

5
On BEST ANSWER

Just give the elements of $M'$ different names to see why:

Define $A=abc$, $B=abcba$, $C=baabc$ and $D=baba$.

Now you can easily check that any set of generators of $M'$ has to include $A$, $B$, $C$ and $D$.

Thus in a free monoid, every different product of those would be a different element. In particular, in a free monoid, you'd have $ADA \ne BC$.

However using the definitions, you get $ADA = abc \cdot baba \cdot abc = abcba \cdot baabc = BC$ (you'll recognize in the middle the equation you gave). Therefore, $M'$ cannot be a free monoid.

Since $M'$ is not a free monoid, it cannot be a free submonoid of $M$. It is, of course, still a submonoid of $M$, it's just not free.