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. 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

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

##
Q. 144) Let n be the positive integer constant and L be the language with alphabet {a}. To recognize L the minimum number of states required in a DFA will be

##
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

##
Q. 146) State table of an FSM is given below. There are two states A And B, one input and one output. Let the initial state be A = 0 and B = 0. To take the machine to the state A = 0 and B = 1 with output = 1 the minimum length of input string required will be

##
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

### Explore Sets

Theory of Computation MCQs Set 1

Theory of Computation MCQs Set 2

Theory of Computation MCQs Set 3

Theory of Computation MCQs Set 4

Theory of Computation MCQs Set 5

Theory of Computation MCQs Set 6

Theory of Computation MCQs Set 7

Theory of Computation MCQs Set 8

Theory of Computation MCQs Set 9

Theory of Computation MCQs Set 10

Theory of Computation MCQs Set 11

Theory of Computation MCQs Set 12

Theory of Computation MCQs Set 13

### Explore More Categories

Click on category to learn MCQs of that category.Electronics and Communication Engineering