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

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?

• Short version: if the total length of the string is odd then there must be different numbers of 0s and 1s left. As long as the string started with the same number of 0s and 1s, then steps 2.2 and 2.3 will remove the same number of 0s and 1s, and thus preserve that property. – Steven Stadnicki Nov 30 '12 at 23:23
• In a slightly more complicated form, this is effectively a search through a (the # of 0s) and b (the # of 1s), checking their low-order bits to confirm that they're the same (this is the 'parity of sum' test), then lopping off the low-order bits (steps 2.2 and 2.3) and continuing. – Steven Stadnicki Nov 30 '12 at 23:24
• You give the algorithm, so I don't get what "How does it work?" asks for. Do you mean to ask why it works? – Raphael Dec 1 '12 at 14:00

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 = 011   OK (14 mod 2 = 6 mod 2 )
11 =  01   OK ( 6 mod 2 = 3 mod 2 )
1 =   0   OK ( 3 mod 2 = 1 mod 2 )
 =       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!