Home / Engineering / Theory of Computation MCQs / Page 15

# Theory of Computation MCQs | Page - 15

Dear candidates you will find MCQ questions of Theory of Computation here. Learn these questions and prepare yourself for coming examinations and interviews. You can check the right answer of any question by clicking on any option or by clicking view answer button.

## `Q. 141) Which of the following statement is false for a turing machine?`

(A) There exists an equivalent deterministic turing machine for every nondeterministic turing machine
(B) Turing decidable languages are closed under intersection and complementation
(C) Turing recognizable languages are closed under union and intersection
(D) Turing recognizable languages are closed under union and complementation

## `Q. 142) Two persons X and Y have been asked to show that a certain problem p is NP-complete. X shows a polynomial time reduction from the 3-SAT problem to p and Y shows a polynomial time reduction from p to 3-SAT. From these reduction it can be inferred that`

(A) P is NP-complete
(B) P is NP-hard but not NP-complete
(C) P is in NP but not NP-complete
(D) P is neither NP-hard nor in NP

## `Q. 143) 3-SAT and 2-SAT problems are`

(A) NP-complete and in P respectively
(B) Undecidable and NP-complete
(C) Both NP-complete
(D) Both in P

(A) 2k + 1
(B) k + 1
(C) 2n + 1
(D) n + 1

## `Q. 145) Consider a stack, which is limited to 10 items. The language accepted by a push- down automaton in such stack is best described as`

(A) Regular
(B) Deterministic context free
(C) Context free
(D) Recursive

(A) 2
(B) 7
(C) 4
(D) 3

## `Q. 147) Out of the three decision problems P1, P2 and P3, P1 is decidable and P2 is undecidable. The statement that holds true is`

(A) P3 is decidable if P3 is reducible to compliment of P2
(B) P3 is decidable if P1 is reducible to P3
(C) P3 is undecidable if P1 is reducible to P3
(D) P3 is undecidable if P2 is reducible to P3

Download our easy to use, user friendly Android App from Play Store. And learn MCQs with one click.