1
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Yuval Filmus Feb 5 '19 at 18:06
  • $\begingroup$ A={0,1} and B={0,1,00,01,10,11} would those two work? $\endgroup$ – James Swanson Feb 5 '19 at 18:27
  • $\begingroup$ Well, $\{0,1\}$ is contained in $B$. $\endgroup$ – Yuval Filmus Feb 5 '19 at 18:28
  • $\begingroup$ isnt {0,1} exclusively not a part of b, because it is the set {0,1} and not the string 01 $\endgroup$ – James Swanson Feb 5 '19 at 18:29
  • 1
    $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Feb 5 '19 at 18:30
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.