Let Lo = {0, 1}1, the language of all binary strings ending in 1. Consider the following DTM accepting Lo: The alphabet is given by = { , B, 0, 1 }. Here is the start symbol, and B is the blank symbol. The set of states is given by Q = {q0,qh,q1,q2 }. q0 is the start state, and qh is the final state. The transition function is defined by: (q0, ) = (q1, , R), (q1,0) = (q1,0,R), (q1,1) = (q1,1,R), (q1,B) = (q2,B,L), (q2,1) = (qh,1,S). We assign binary code to alphabet symbols as follows: = 00, B = 11, 0 = 01, 1 = 10. We assign binary code to states as follows: q0 = 00, qh = 11, q1 = 01, q2 = 10. We define

the ith snapshot of computation as the binary encoding of the pair (qi,ai) such that in ith step, the TM head is scanning the symbol ai, and it is in state qi. For example, Z1 = (q0,) = 0000. A CNF formula is written corresponding to input 11 to the TM, using the polynomial-time reduction L p SAT for any language L in NP (as discussed in the lecture: Zi+1 is a function of Zi, Zf(i+1), and g(i+1), where g(i) is the head position at step i, and f(i) is the largest number of step j such that in jth step the head was at the same position as the ith step, where j < i and if no such j exists then f(i) = 0). Let X11, X12, X21, and X22 be the variables corresponding to the binary encoding of an input of length 2. The given TM runs for 6 steps on input 11. Let Zij be the variable corresponding to jth bit of Zi (1 i 6,1 j 4). Below is given a CNF formula that encodes the computation of the given TM on input 11 using the given reduction. Some variables are missing in the formula (Wk for 1 k 10). You have to write the correct variable (out of only Zij or Zij for 1 i 6, 1 j 4) corresponding to each Wk (1 k 10) in correct order according to the given reduction. Let the function (u1,u2,u3,u4,u5,u6) be defined as a 6CNF formula having 59 clauses in all possible combinations of the 6 literals (either a variable ul or its complement ul for 1 l 6) except for the following 5 clauses: (u1 u2 u3 u4 u5 u6), (u1 u2 u3 u4 u5 u6), (u1 u2 u3 u4 u5 u6), (u1 u2 u3 u4 u5 u6), and (u1 u2 u3 u4 u5 u6). Think how is generated from the transition function. Let the function (v1, v2, v3, v4) be defined as a 2CNF formula: (v1,v2,v3,v4) = (v1 v3)(v1 v3)(v2 v4)(v2 v4). Think what is the role of . The CNF formula is given as: (X11)(X12)(X21)(X22)(Z11)(Z12)(Z13)(Z14)(Z11, Z12, Z13, Z14, Z21, Z22)(W1)(W2)(Z21, Z22, Z23, Z24, Z31, Z32)(W3)(W4)(Z31, Z32, Z33, Z34, Z41, Z42) (W5)(W6)(Z41, Z42, Z43, Z44, Z51, Z52)(Z53, Z54, W7, W8)(Z51, Z52, Z53, Z54, Z61, Z62) (Z63, Z64, W9, W10) (Z61) (Z62). The above formula follows the sequence: input is correct, TM starts correctly, computation is according to the transition function of the

TM, and finally TM halts correctly. Which option is correct?

13. W4 =

(a) Z32 (b) Z33 (c) Z34 (d) Z34 (e) Z32 (f) Z33 (g) Z34 (h) Z34

14. W5 =

(a) Z41 (b) Z42 (c) Z43 (d) Z44 (e) Z41 (f) Z42 (g) Z43 (h) Z44

15. W6 =

(a) Z41 (b) Z42 (c) Z43 (d) Z44 (e) Z41 (f) Z42 (g) Z43 (h) Z44