1
$\begingroup$

I have the set:

B = {x ∈ {0,1}* | there is an equal number of 0's and 1's in x}

and therefore,

B* = {e,01,10,0011,0101,0110,1100,1010,1001,....etc}

I need to either prove or disprove that B*=B

I believe they are equal, because B* is just the concatenation of one string onto another. I think the trick is since the 0's and 1's have to be of equal number, that concatenating strings would keep the same number of 0's and 1's the same.

I just need a little help in the right direction as to prove B*=B. I was thinking of showing that if

B⊆B* and B*⊆B, that B*=B holds.

Any help would be much appreciated!

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ What prevents from showing that $B\subseteq B^*$ and $B^*\subseteq B$? (hint: one these is true independent of the definition of $B$). Have you tried it? Where did you get stuck? $\endgroup$ – Discrete lizard♦ Feb 4 at 20:46
  • $\begingroup$ So i know B⊆B∗ no matter what B is, just from the definition of B*. What is more difficult is proving that B∗⊆B. I tried making an arbitrary string x in B*, but most proofs involving subsets, there is an equation that must hold. For B* I do not know exactly what property I must use other than my intuition with the concatenation and how the number of 0's and 1's will remain the same. $\endgroup$ – Ben Feb 4 at 21:17
  • $\begingroup$ " my intuition with the concatenation and how the number of 0's and 1's will remain the same" Your intuition seems right. Now you have to prove it. Induction on the length of the string in B* seems a reasonable approach. $\endgroup$ – Discrete lizard♦ Feb 4 at 21:24
3
$\begingroup$

(Criterion of no-op Kleene star) Let $V$ be a language such that $\epsilon\in V$. Then $V=V^*$ if and only if $V=VV$, where $V^*$ is the Kleene star.

Proof: "$\Longrightarrow$": $V=V\epsilon\subseteq VV$ while $VV\subseteq V^*=V$.

"$\Longleftarrow$". $V\subseteq V^*$ by definition. Let $V_i$ as defined in Wikipedia. Since $V_0\subseteq V$ and assuming $V_n\subseteq V$, $V_{n+1}=V_nV\subseteq VV=V$, we know $V_i\subseteq V$ for all $i\ge0$ by induction. Hence $$V^*=\bigcup_{i=0}^\infty V_{i+1}\subseteq \bigcup_{i=0}^\infty V=V\,.$$

Exercise 1. Show that $\epsilon\in B$ and $B=BB$.

Exercise 2. Let $V$ be a non-empty language such that $V=VV$. Show that $\epsilon\in V$. (Hence for a non-empty language $V$, $V=V^*$ if and only if $V=VV$.)

Exercise 3. Show that $V^*=(V^*)^*$.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

I believe you're on the right track. I would try to write this formally as proofs. It's been a while since I've been in discrete math but I would argue something along the lines of

Given B = {x ∈ {10,01}* |s.t. there is an equal number of 0's and 1's in x}

Given there are an equal number of 0's and 1's in x, the difference between 0's and 1's are zero. (There may be a formal proof missing here...)

Given B* = {y ∈ {Bn + Bm} | s.t. Bn and Bm are both a subset of B and B* is the concatenation of 2 subsets of B.

Therefor ANY y is a concatenated of some subset B which each have an equal sum of 0's and 1's, thus the sum of total 0's and 1's of any subset B combination would also sum to an even number of 0's and 1's.

A bit wordy but the best I could do for now.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I am afraid that I would not say there is a formal or even informal proof in this answer. The description of $B^*$ just manifests itself from nowhere. That description and the following explanation is so fuzzy that it sounds like the kind of explanation that might be understood by all who had understood and that will not be easy to be understood by anybody who had not understood. $\endgroup$ – Apass.Jack Feb 4 at 22:21
  • $\begingroup$ It doesn't really manifest from nowhere though, I think orlp made a good step towards an official proof. Look at the proof for even numbers and try to re-use that cs.stanford.edu/~jtysu/proofs.pdf $\endgroup$ – Zakk Diaz Feb 5 at 19:10
0
$\begingroup$

Hint: let $a=01$ and $b=10$ and argue about $\{a, b\}^*$.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

HINT:

Let $w$ be a string in $B*$. Then $w$ is the concatenation of 0 or more strings from $B$, i.e. $w = v_1v_2v_3\ldots v_k$, where each $v_i \in B$. Now consider how many $0$s and $1$s are in $w$. How many $0$s does $v_1$ contribute? How many $1$s does $v_1$ contribute? Can you write the difference between the number of $1$s and $0$s in $w$ as a summation over $v_i$?

Also keep in mind that $w$ could be $\epsilon$, which you may want to handle as a separate case.

|cite|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.