How does this algorithm for verifying if a string is $0^n1^n$ work?

Question

I have found an efficient algorithm for verifying if a string $\omega$ is of the form $0^n1^n$, where $n \in \mathbb{N}$.

1. Scan across $\omega$. If a 1 appears before a 0, then reject.

2. Repeat so long as some 0s and some 1s remain on the tape.

   1. Scan across $\omega$. If the total number of 0s and 1s remaining is odd, reject.
   2. Scan across $\omega$. Cross out every other 0 starting with the first 0.
   3. Scan across $\omega$. Cross out every other 1 starting with the first 1.

3. If no 0s and 1s remain in $\omega$, accept. Otherwise, reject.

I generally see how this algorithm is efficient. It gets rid of half of all 1s and 0s every iteration. How does it work though? Why must we reject if the total number of 0s and 1s remaining in $\omega$ is odd?

Answer 1

This is a very informal answer (other users will give you a more formal and concise answer :-)

Suppose you have two numbers written in binary notation (the smaller one left-padded with zeros); for example:

14 =  1110
 6 =  0110

A simple algorithm to check if they are equal is comparing the two binary representations bit by bit; this can be done comparing the lower bit and then dividing the number by two (i.e. dropping the lower bit):

111[0] = 011[0]   OK (14 mod 2 = 6 mod 2 )
 11[1] =  01[1]   OK ( 6 mod 2 = 3 mod 2 )
  1[1] =   0[1]   OK ( 3 mod 2 = 1 mod 2 )
   [1] =    [0]   NO => 14 and 6 are different

You can easily notice that the lower bits of two numbers are the same if the numbers are both even or both odd (i.e. if their sum is even).

The algorithm above does exactly the same thing but the numbers are represented in unary:

00000000000000 111111   even 0s, even 1s, sum even OK
-0-0-0-0-0-0-0 -1-1-1   odd 0s, odd 1s, sum even OK
---0---0---0-- ---1--   odd 0s, odd 1s, sum even OK
-------0------ ------   odd 0s, even 1s, sum odd REJECT!