Consider the set of all binary strings which is $\{0, 1\}^∗$
Now I want to prove the following:
(A) Prove that $\{0,1\}^* = \{1\}^* (\{0\}\{0\}^*\{1\}\{1\}^*)^*\{0\}^*$
(B) Prove that the elements of $\{0,1\}^*$ are uniquely created on the right-hand side of this equality.
Here is what I have done so far.
Each element $ \alpha \in \{0,1\}^*$ has $k$ occurrences of $0$ for some $k$. Thus we can write $\alpha = b_1 0 b_2 0 ... b_k 0 b_{k+1}$ , where $b_i$ are consisting of 1's. So $b_i \in \{1\}^*$. Hence we can see that
$\{0,1\}^* = \{1\}^* (\{0\}\{1\}^*)^*$
Now I want to continue from this expression.
However, I dont have a clue how to do so with the same argument. I also tried proving inclusions, but wasn't successful.
Any help would be much appreciated.
(A) It is true that $X = \{0,1\}^* = \{1\}^* (\{0\}\{0\}^*\{1\}\{1\}^*)^* \{0\}^* = Y$
Proving that is by showing that (A1) every element in $Y$ is in $X$ & (A2) every element in $X$ is in $Y$
I will elaborate the Proof in Excruciating Detail (a term I came across here at MSE !) though that is not really necessary when OP gets experience.
(A1) Consider a String $S$ in $Y$ : It is made of Digits $0$ & $1$
Naturally , $S$ must occur in $X$ which is the Set of all Binary Strings.
(A2) We can check that Null String , $0$ , $1$ , $01$ , $10$ will all match the Pattern & will occur $Y$.
Consider a longer String $S$ in $X$ which might or might not start with $1$ & might or might not end with $0$
$S=1^*(0Z_1Z_2Z_3 \cdots Z_n1)0^*$
We can match the Initial Block of $1$ Digits to $\{1\}^*$ , where that Block might be Null String.
We can then match the terminal Block of $0$ Digits to $\{0\}^*$ , where that Block might be Null String.
We have then taken $S=1^*(0Z_1Z_2Z_3 \cdots Z_n1)0^*$ to removed the Initial Block & terminal Block to leave the Central Block $(0Z_1Z_2Z_3 \cdots Z_n1)$
Because the Central Block starts with $0$ & terminates with $1$ , we can see that every $0$ Sequence must have a following $1$ Sequence.
We can match every such Sequence against $(\{0\}\{0\}^*\{1\}\{1\}^*)$
which we can repeat the necessary number of times.
Hence every String in $X$ occurs in $Y$
$X=Y$
(B) Uniqueness is true here.
Consider $1010101010101010$ : The $0$ Digits in the Central Block can match either against $\{0\}$ or against $\{0\}\{0\}^*$
Likewise , the $1$ Digits in the Central Block can match either against $\{1\}$ or against $\{1\}\{1\}^*$
Provided we have the ${D}^+$ Operation to indicate matching $1$ or more Digits ( which is Equivalent to the ${D}{D}^*$ Operation ) , we can write it like this :
$X = \{0,1\}^* = \{1\}^* (\{0\}^+\{1\}^+)^* \{0\}^* = Y$
Now , we match :
a Block of all $1$ Digits (which might be Empty)
followed by (Zero or more) alternating Blocks of all $0$ Digits and all $1$ Digits
terminated by a Block of all $0$ Digits (which might be Empty)
This is unique.