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

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.

• I would suggest that you make up your mind on whether it is $a$ and $b$, or $0$ and $1$, and that you edit the question accordingly. You should probably use $0$ and $1$ since it is used in the diagram. – babou Jun 19 '15 at 21:46
• Please transcribe the first image using code formatting. – Raphael Jun 19 '15 at 23:07
• @Raphael can you recommend how I could find out how to do that? – CodyBugstein Jun 19 '15 at 23:09
• Sure. Just click the little question mark above the textbox you reach by clicking "edit" beneath your post. – Raphael Jun 19 '15 at 23:12
• What have you tried? Have you tried running the machine by hand on a few inputs, to see what it does? This should be your first step. We expect you to make a serious effort to answer your question on your own before asking here, and to tell us what you tried and where you got stuck in the question. – D.W. Jun 19 '15 at 23:39

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).

The machine just changes the $O$ to $A$ and the $1$ to $B$, in such a way that it changes a $1$ each time it has changes a $0$. Hence, if there is the same number of $0$ and $1$, they all end up being changed at some point. The TM no longer finding any $0$ will go to the bottom part of the diagram and check that all $1$ have been changed to $B$, i.e. that the sequence of $B$ is followed by a blank space. In that case it accepts.

But is some $1$ is left after the $B$, then the TM will block in state $q_3$ (no transition corresponding to $1$ on the tape) and reject. Indeed, that means hat there were more $1$ than $0$, which does not conform.

But if there were more $0$ than $1$, say $0^n1^m$ with $n>m$, the TM will block in state $q_1$. The reason is that, after erasing $m$ symbols $0$ and correspondingly $m$ symbols $1$, the TM will erase another $0$, and try in state $q_1$ to find another $1$ to erase. But it will find none, only a blank space.