MCQ:

We wish to perform the reduction of acceptance by a Turing machine to MPCP. We assume the TM M satisfies Theorem 8.12: it never moves left from its initial position and never writes a blank. We know the following:

1.The start state of M is q.

2. r is the accepting state of M.

3. The tape symbols of M are 0, 1, and B (blank).

4.One of the moves of M is (q,0) = (p,1,L).

Which of the following is DEFINITELY NOT one of the pairs in the MPCP instance that we construct for the TM M and the input 001?

(a) (0r1, r)

(b) (0r, r)

(c) (0, 0)

(d) (0q1, q)