Let's say you have a binary string made up of $0$ and $1$ (e.g. $0011111$). Order does not matter so we can always put $0$s before $1$s. For ease of notation, we will write $0^n$ when we mean exaclty $n$ zeros. For example, $0^41^ 2 = 000011$.
Rule 1: You can replace a $1$ with $11$. This can be written as $1$ $→$ $11$.
Rule 2: You can replace $11$ with $0$. This can be written as, $11$ $→$ $0$.
Rule 3: $00$ can be erased. This can be written as $00$ $→$ $null$.
Rule 4: $1 → 000$.
Rule 5: $0 → 111$.
Rule 6: $11 → 00$.
How do you prove that $0^n$$1^ n$ → null is possible using only Rules 3–6?
So far I can prove that $0^n$$1^ n$ → null using Rules 1-3. Since any $1$ can be turned into $11$ and any $11$ can be turned into $0$, $1$ can be turned into $0$. Also since $1$ can be turned into $11$, you can add $1$ to any binary string. This means that with $0^n$$1^ n$ you can always get an odd number of $0$s meaning you can always get null.
