Binary String Combinations

binary

For this question, imagine finite binary strings consisting of $0$ and $1$.
For instance, $00111$ is a string. Order does not matter, so the string $1100$ is
considered equivalent to $0011$. We will therefore always write $0$s before writing $1$s.
For ease of notation, we will write $0^{n}$ when
we mean exaclty $n$ zeros. Therefore,
$0^{4}1^{2}=000011$. These exponents do
not indicate multiplication!

Here are three rules for manipulating a string:

Rule 1: You may always replace a $1$ with $11$. We will write this as $1 \stackrel{1}{\rightarrow} 11$.

Rule 2: You may replace $11$ with a $0$. More succinctly,
$11 \stackrel{2}{\rightarrow} 0$.

Rule 3: You may erase $00$. We can write this as
$00 \stackrel{3}{\rightarrow} \mbox{ null}$.

The following sequence is legal:
$0^41^{2}=\underline{\bf 00}0011 \stackrel{3}{\rightarrow} \underline{\bf 00}11 \stackrel{3}{\rightarrow}
\underline{\bf 11} \stackrel{2}{\rightarrow} 0. $

Therefore, the string $0^{4}1^{2}$ has been transformed into the string $0$, and
we can write $0^{4}1^{2} \rightarrow 0$. For any bean counters out there, we used Rule 2 once
and Rule 3 twice. We did not use Rule 1 at all. Note that, for clarity, we have boldfaced
and underlined the characters that are being operated on.

  1. Prove or disprove
    $0^{3}1^{3} \rightarrow {\tt null}$.

  2. Let $0^{n}1^{n}$ denote a string with $n$ zeros
    followed by $n$ ones. Prove or disprove $0^{n}1^{n}
    \rightarrow {null}$    .

  3. What can you say about $0^{m}1^{n}$?

Best Answer

What can you say about combining rule 1 and 2 ?

It flips ones into zeroes, indeed $1\to 11\to 0$

So what does it do to $1^n$ ?

prove by induction $1^n\to 0^n$

What does rule 3 applied repeatedly do to a string of only zeroes ?

it removes any pair of zeroes, so $0^{2p}\to\tt{null}$ and $0^{2p+1}\to 0$

Can you modify the number of $1$ ?

Yes notice that by rule 1 we can append as many additional $1$ as wanted, in particular if $n>0$ (if there is at least one $1$) then $1^n\to 1^{n+1}$

Conclude

$0^m1^n\to 0^m0^n=0^{m+n}\to 0\text{ or }\tt{null }$ depending on the parity of $m+n$, but since we can turn $m+n$ even by appending some $1$ then we are always able to eventually land on $\tt{null}$.

Related Question