Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
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

1 Answer 1

up vote 4 down vote accepted

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!
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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