How does this Turing machine accept $a^n b^n$?

Problem Detail: 

I'm reading this tutorial from the University of Illinois about Turing Machines, and I don't understand something.

They give a pseudocode algorithm for an machine that accepts strings from the language

$L = {0^n1^n}$

and a diagram of the machine. Both are pictured below:

What I don't understand however is how does this machine know that the number of $0$s are the same as the number of $1$s. I see no mechanism that can do that. All it seems the machine can do is recognize that there are no $0$s after $1$s.

Asked By : CodyBugstein

Answered By : Yuval Filmus

It might be helpful to see what happens when the machine encounters $0^31^3$, say:

1. Initial state: $000111$.
2. Mark the first unmarked zero: $A00111$.
3. Mark the first unmarked one: $A00B11$.
4. Mark the first unmarked zero: $AA0B11$.
5. Mark the first unmarked one: $AA0BB1$.
6. Mark the first unmarked zero: $AAABB1$.
7. Mark the first unmarked one: $AAABBB$.
8. There are no unmarked zeros and no unmarked ones, so accept.

In contrast, here is what happens on input $00011$:

1. Initial state: $00011$.
2. Mark the first unmarked zero: $A0011$.
3. Mark the first unmarked one: $A00B1$.
4. Mark the first unmarked zero: $AA0B1$.
5. Mark the first unmarked one: $AA0BB$.
6. Mark the first unmarked zero: $AAABB$.
7. Crash (reject) since there are no remaining unmarked ones.

And here is what happens on input $00111$:

1. Initial state: $00011$.
2. Mark the first unmarked zero: $A0111$.
3. Mark the first unmarked one: $A0B11$.
4. Mark the first unmarked zero: $AAB11$.
5. Mark the first unmarked one: $AABB1$.
6. There are no unmarked zeroes but there is an unmarked one, so crash (reject).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/43762