Prentice-Hall     Addision-Wesley

Copyright © 2007 Gradiance Corporation.

 

Gradiance Online Accelerated Learning

 

 

 

 

 

     

Turing Machines

 

 

1.  

A Turing machine M with start state q0 and accepting state qf has the following transition function:

δ(q,a)

0

1

B

q0

(q0,1,R)

(q1,1,R)

(qf,B,R)

q1

(q2,0,L)

(q2,1,L)

(q2,B,L)

q2

-

(q0,0,R)

-

qf

-

-

-

Deduce what M does on any input of 0's and 1's. Hint: consider what happens when M is started in state q0 at the left end of a sequence of any number of 0's (including zero of them) and a 1. Demonstrate your understanding by identifying the true transition of M from the list below.

 

 

 

 a) 

q01100 |-* 1101Bqf

 

 b) 

q01010 |-* 0101Bqf

 

 c) 

q01010 |-* 0101qf

 

 d) 

q00101 |-* 1110Bqf

 

 

 

 

 

2.  

The Turing machine M has:

  • States q and p; q is the start state.
  • Tape symbols 0, 1, and B; 0 and 1 are input symbols, and B is the blank.
  • The following next-move function:

State

Tape

Move

 

Symbol

 

q

0

(q,0,R)

q

1

(p,0,R)

q

B

(q,B,R)

p

0

(q,0,L)

p

1

none (halt)

p

B

(q,0,L)

Simulate M on the input 1010110, and identify one of the ID's (instantaneous descriptions) of M from the list below.

 

 

 

 a) 

10q10110

 

 b) 

10101p10

 

 c) 

00000p10

 

 d) 

1010q110

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3.  

A nondeterministic Turing machine M with start state q0 and accepting state qf has the following transition function:

δ(q,a)

0

1

B

q0

{(q1,0,R)}

{(q1,0,R)}

{(q1,0,R)}

q1

{(q1,1,R), (q2,0,L)}

{(q1,1,R), (q2,1,L)}

{(q1,1,R), (q2,B,L)}

q2

{(qf,0,R)}

{(q2,1,L)}

{}

qf

{}

{}

{}

Simulate all sequences of 5 moves, starting from initial ID q01010. Find, in the list below, one of the ID's reachable from the initial ID in EXACTLY 5 moves.

 

 

 

 a) 

0111q1

 

 b) 

0q2110

 

 c) 

00101q1

 

 d) 

01101q1

 

 

 

 

 

4.  

A nondeterministic Turing machine M with start state q0 and accepting state qf has the following transition function:

δ(q,a)

0

1

B

q0

{(q1,0,R)}

{(q1,0,R)}

{(q1,0,R)}

q1

{(q1,1,R), (q2,0,L)}

{(q1,1,R), (q2,1,L)}

{(q1,1,R), (q2,B,L)}

q2

{(qf,0,R)}

{(q2,1,L)}

{}

qf

{}

{}

{}

Deduce what M does on any input of 0's and 1's. Demonstrate your understanding by identifying, from the list below, the ID that CANNOT be reached on some number of moves from the initial ID q00011000.

 

 

 

 a) 

0q20111001

 

 b) 

0qf1111111

 

 c) 

011111111q1

 

 d) 

0qf11111111111

 

 

 

 

 

5.  

The Turing machine M has:

  • States q and p; q is the start state.
  • Tape symbols 0, 1, and B; 0 and 1 are input symbols, and B is the blank.
  • The following next-move function:

State

Tape

Move

 

Symbol

 

q

0

(q,0,R)

q

1

(p,0,R)

q

B

(q,B,R)

p

0

(q,0,L)

p

1

none (halt)

p

B

(q,0,L)

Your problem is to describe the property of an input string that makes M halt. Identify a string that makes M halt from the list below.

 

 

 

 a) 

001010

 

 b) 

0110

 

 c) 

00001

 

 d) 

0000