Determine if given set is a free submonoid.

Question

Determine such A, that $A^*$ is a free submonoid of $\{a,b,c,d,e,f,g\}^*$.

A) $A = \{ ae, b,c,de\}$

B) $A = \{ ade, ddbee,dfc,dgd\}$

C) $A = \{ a, ab,bc,c\}$

D) $A = \{ ab, ba ,ca\}$

E) $A = \{ ab, abc,cde ,de\}$

Please help: What is the best/fastest to test it?

Multiplying elements of $A$, you can not obtain some word by two different mean. For instance, in E), $abcde=abcde=abcde$. So you can eliminate E). — Thibaut Dumont, Jun 15 '15 at 09:18

score 0 · Answer 1 · answered Jun 15 '15 at 13:09

You could use the general purpose Sardinas–Patterson algorithm.

However, your examples can be easily solved directly: $A$, $B$ and $D$ are prefix codes and Thibaut Dumont already observed that $E$ is not a code since $abcde$ can be written in two different ways. Similarly, in $C$, $(a)(bc) = (ab)(c)$ and thus $C$ is not a code.

Determine if given set is a free submonoid.

1 Answers1