Home / Engineering / Theory of Computation MCQs / Page 7

# Theory of Computation MCQs | Page - 7

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. 62) Let S be an NP-complete problem, Q and R be two other problems not known to be in NP. Q is polynomial-time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?

##
Q. 63) For s Є (0+1)* let d(s) denote the decimal value of s(e.g.d(101)) = 5 Let L = {s Є (0+1)* d(s) mod 5=2 and d(s) mod 7 != 4} Which one of the following statements is true?

##
Q. 64) A FSM can be considered, having finite tape length without rewinding capability and unidirectional tape movement

##
Q. 65) Which of the following statement is true?

##
Q. 66) Recursively enumerable languages are not closed under

##
Q. 67) The following CFG is in
S → aBB
B → bAA
A → a
B → b

##
Q. 68) The languages -------------- are the examples of non regular languages.

##
Q. 69) Let L be any infinite regular language, defined over an alphabet Σ then there exist three strings x, y and z belonging to Σ such that all the strings of the form XY^ n Z for n=1,2,3, … are the words in L called

##
Q. 70) Languages are proved to be regular or non regular using pumping lemma.

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