what is number of states in following Turing m/c?

Question

What are the min number of states in Turing machine L={0^n 1^n}

As per below link we need 4 states including final state ....

But cant we do in 3 states....?

For identifying 1st 0 convert it to X(change state from q0 to q1), then bypass all 0 , on reaching 1st 1 convert to Y(change state from q1 to q2) and move left ....by pass all 0 to reach last X in leftmost end...change state to q0 ...so that we can again follow same process....but why a change of state is required when all 0s have been converted to X....?Why do we need q3.....?

http://www.eecs.wsu.edu/~ananth/CptS317/Lectures/TuringMachines.pdf

Please explain..................

Answer 1

As per your explanation, first 0 is converted into X, and then reach to first 1 that is converted in Y and so on [ 0 to X, 1 to Y]

using 3 states, q0,q1 and q2 . [000111BBB.. to XXXYYYBBB..]

Then why we need q3, To ensure all 0's is converted into X, we need to check there is a Y in right of X 

[what if we reach q2 to q0, and there is no more 0's at q0]

for example 000111BBB... lead to X00Y11BBB.. leads to XX0YY1BBB.. leads to XXXYYYBBB... using q0,q1,q3.

B is blank symbol.

Then why we need q4, suppose we have input 0001111BBB..

that will lead to XXXYYY1BBB.. that should not be accept in TM.

so q3 ensure there is Y in right of X(all 0's is converted to X ) , q4 to ensure after all Y there is B (Blank symbol) 

[ what if 1's are more than 0's]

so 5 states are required.

Our purpose is not only to convert all 0's to X and 1's to Y, but to ensure input of language ( w ∊L) is accepted and else (w∉ L) is to rejected

Answer 2

TM for {0n1n | n≥1}
Next Tape Symbol
Curr. 0 1 X Y B
State
q0 (q1,X,R) - - (q3,Y,R) -
q1 (q1,0,R) (q2,Y,L) - (q1,Y,R) -
q2 (q2,0,L) - (q0,X,R) (q2,Y,L) -
q3 - - - (q3,Y,R) (q4,B,R)
*q4 - -- - - -