Question

Theory of Computation 2. (a) Show that the language B e,1, 11,1100 is in complexity class TIME ) b) Show that the language B e, 1,11,1100 is in complexity class P.

Answer 1

a. Language B is in complexity class TIME(1) because this language B can be recognized by deterministic Turing machine in time O(1). Below is the deterministic Turing Machine to recognize B.

(q_o, € ) --> (q_accept, €, R)//accept the empty string

(q_o, 1) -> (q₁ , 1, R) //move right if input 1

(q₁, €) --> (q_accept ,€, R) //accept if input is 1

(q₁ , 1) --> (q₂, 1, R)

(q₂, €) --> (q_accept, €, R) //accept if input is 11

(q₂, 0) -> (q₃, 0, R)

(q₃, 0) --> (q₄, 0, R)

(q₄, €) --> (q_accept, 1, R) //accept if input is 1100

We can see that input will be accepted only if it is in set B and there are constants steps to decide B, hence B is in complexity class TIME(1).

b. Since B is in complexity class TIME(1) which is subset of class P, hence B is also in class P.

Please comment for any clarification.