# $A^* = B^*$ with $\{0,1\}$ contained in $A$ but not in $B$

I'm trying to exhibit two formal languages $$A,B ⊆ \{0,1\}^*$$ such that $$A^* = B^*$$ and $$\{0,1\}$$ is contained in $$A$$ but not in $$B$$.

Finding a language for $$A$$ is very easy, but I get stuck on $$B$$, because since $$A^*=B^*$$, and A has $$\{0,1\}$$, that $$B^*$$ must also have $$\{0,1\}$$. I can't think of a language that has $$\{0,1\}$$ in $$B^*$$ but would not be in $$B$$. Maybe I'm missing something.

• If $0 \in A$ then $0 \in A^* = B^*$ and so $0 \in B$. Similarly $1 \in B$. So this is impossible. Perhaps you got the question wrong? – Yuval Filmus Feb 5 at 18:06
• A={0,1} and B={0,1,00,01,10,11} would those two work? – James Swanson Feb 5 at 18:27
• Well, $\{0,1\}$ is contained in $B$. – Yuval Filmus Feb 5 at 18:28
• isnt {0,1} exclusively not a part of b, because it is the set {0,1} and not the string 01 – James Swanson Feb 5 at 18:29
• You haven't explained what "contained" means (in fact, you used a different word), but assuming the usual meaning "$\subseteq$", then $\{0,1\}$ is certainly contained in your $B$. – Yuval Filmus Feb 5 at 18:30

If $$0 \in A$$ then clearly $$0 \in A^* = B^*$$. Conversely, if $$0 \in B^*$$ then $$0 \in B$$: indeed, if $$0 = w_1 \ldots w_n \in B$$, then exactly one of the $$w_i$$ can be non-empty, and it must equal $$0$$. Therefore $$\{0,1\} \subseteq A$$ and $$A^* = B^*$$ implies $$\{0,1\} \subseteq B$$. In other words, there are no two languages $$A,B$$ satisfying your constraints.