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?

  • $\begingroup$ 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. $\endgroup$ Nov 30, 2012 at 23:23
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 30, 2012 at 23:24
  • $\begingroup$ You give the algorithm, so I don't get what "How does it work?" asks for. Do you mean to ask why it works? $\endgroup$
    – Raphael
    Dec 1, 2012 at 14:00

1 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!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.