EXAMPLE 3.9 The following is a formal description of M₁ = (Q, E, F, 8, 91, accept, reject), the Turing machine that we informally described (page 167) for deciding the lan- = {w#w| w = {0,1}*}. guage • B = Q = {91,..., 98, qaccept, reject}, • Σ = {0,1,#}, and I = {0,1,#,x,u}. • We describe & with a state diagram (see the following figure). The start, accept, and reject states are 91, accept, and reject, respectively. 0,1→R 92 #→R x->R 94 0-x,R 0-x, L 91 #→R 1-x,R 98 X-R 93 0,1-R #→R 95 x-R Jaccept 1-x,L 96 #→L 0,1,x→L x-R 97 0,1-L d. 000000. 3.2 This exercise concerns TM M1, whose description and state diagram appear in Ex- ample 3.9. In each of the parts, give the sequence of configurations that M₁ enters when started on the indicated input string. A a. 11. b. 1#1. C. 1##1. d. 10#11. e. 10#10.

EXAMPLE 3.9 The following is a formal description of M₁ = (Q, E, F, 8, 91, accept, reject), the Turing machine that we informally described (page 167) for deciding the lan- = {w#w| w = {0,1}*}. guage • B = Q = {91,..., 98, qaccept, reject}, • Σ = {0,1,#}, and I = {0,1,#,x,u}. • We describe & with a state diagram (see the following figure). The start, accept, and reject states are 91, accept, and reject, respectively. 0,1→R 92 #→R x->R 94 0-x,R 0-x, L 91 #→R 1-x,R 98 X-R 93 0,1-R #→R 95 x-R Jaccept 1-x,L 96 #→L 0,1,x→L x-R 97 0,1-L d. 000000. 3.2 This exercise concerns TM M1, whose description and state diagram appear in Ex- ample 3.9. In each of the parts, give the sequence of configurations that M₁ enters when started on the indicated input string. A a. 11. b. 1#1. C. 1##1. d. 10#11. e. 10#10.