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

(A) (L1)’ is recursive and (L2)’ is recursively enumerable
(B) (L1)’ is recursive and (L2)’ is not recursively enumerable
(C) (L1)’ and (L2)’ are recursively enumerable
(D) (L1)’ is recursively enumerable and (L2)’ is recursive
View Answer Discuss Share

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?

(A) R is NP-complete
(B) R is NP-hard
(C) Q is NP-complete
(D) Q is NP-hard
View Answer Discuss Share

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?

(A) L is recursively enumerable, but not recursive
(B) L is recursive, but not context-free
(C) L is context-free, but not regular
(D) L is regular
View Answer Discuss Share

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

(A) Turing machine
(B) Pushdown automata
(C) Context free languages
(D) Regular languages
View Answer Discuss Share

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

(A) All languages can be generated by CFG
(B) The number of symbols necessary to simulate a Turing Machine(TM) with m symbols and n states is mn.
(C) Any regular languages have an equivalent CFG.
(D) The class of CFG is not closed under union.
View Answer Discuss Share

Q. 66) Recursively enumerable languages are not closed under

(A) Complementation
(B) Union
(C) Intersection
(D) None of the above
View Answer Discuss Share

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

(A) Chomsky normal form but not strong Chomsky normal form
(B) Weak Chomsky normal form but not Chomsky normal form
(C) Strong Chomsky normal form
(D) Greibach normal form
View Answer Discuss Share

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

(A) PALINDROME and PRIME
(B) PALINDROME and EVEN-EVEN
(C) EVEN-EVEN and PRIME
(D) FACTORIAL and SQURE
View Answer Discuss Share

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

(A) Complement of L
(B) Pumping Lemma
(C) Kleene’s theorem
(D) None in given
View Answer Discuss Share

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

(A) True
(B) False
(C) Not always true
(D) can’t say anything
View Answer Discuss Share