Theory of Computation MCQs | Page - 7

Q. 61) Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

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.