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

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

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

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

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

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

(A) Complementation
(B) Union
(C) Intersection
(D) None of the above

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

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

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

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

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