TOC(CS8501) unit- v -mcq PDF

Preview

Summary

Multi Choice Questions and Answers for UNIT V- as per regulation 2017 ...

Description

JAYA ENGINEERING COLLEGE DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING MULTI CHOICE QUESTIONS AND ANSWERS SUBJECT/CODE: THEORY OF COMPUTATION/CS8501

CLASS: III YR CSE

UNIT V 1. When problem is said to be un-decidable? A) There exists an algorithm to find answer of the problem is yes or no. B) There is no algorithm to find answer of the problem is yes or no. C) There is no algorithm to find answer of the problem is yes. D) There is an algorithm to find answer of the problem is yes. Answer: B 2. When problem is said to be decidable? A) There exists an algorithm to find answer of the problem is yes or no. B) There is no algorithm to find answer of the problem is yes or no. C) There is no algorithm to find answer of the problem is yes D) There is an algorithm to find answer of the problem is yes. Answer: A 3. What are recursive enumerable languages? A) There exists a PDA to accept the languages. B) There exists a Turing Machine to accept the languages. C) There exists a Finite Automata to accept the languages. D) None of the mentioned Answer: B 4. A recursive language is also called A) Decidable B) Undecidable C) Both (a) and (b) D) None of these Answer: A 5. Recursive languages are A) Accepted by Turing Machine B) Accepted by Finite Automata C) Both (a) and (b) D) None of these Answer: A 6. Which of the following statement is false? A) The union of two recursively enumerable language is recursively enumerable B) Let L1 and L2 are two recursive language then the union of L1 and L2 i.e. L1 U L2 is also recursive C) If a language L and its complement L- are both recursively enumerable then L is recursive language D) None of these Answer: D 7. Which is false about recursive languages? A) The language is recursive then it is decidable. B) The language is not recursive then it is undecidable C) There exists a Turing Machine to accept the languages. D) The complement of recursive language is neither recursive nor non recursive Answer: D

8. L = {w | M is a DFA and M recognizes input w} where L is -------- . A) Un-decidable B) Decidable C) Non finite D) None of the mentioned. Answer: B 9. PCP stands for A) Posts Correspondence Problem B) Posts Computable Problem C) Prefix Computable Problem D) Postfix Correspondence Problem Answer: A 10.

MPCP stands for A) Many Posts Correspondence Problem B) Many Posts Correspondence Problem C) Modified Posts Correspondence Problem D) Merged Posts Correspondence Problem Answer: C 11. A language L is said to be ____________ if there is a Turing machine M such that L(M)=L and M halts at every point. A) Turing acceptable B) Decidable C) Undecidable D) None of the mentioned Answer: B

12. The complement of recursive language is A) recursive B) neither recursive nor non recursive C) non recursive D) recursive or non recursive Answer: A 13. Recursively enumerable language are closed under A) Concatenation B) Intersection C) Union D) All of these Answer: D 14. The class of unrestricted language corresponds to A) PDA B) TM C) LBA D) FA Answer: B 15. ‟MPCP is un decidable problem ‟ is ----------- ? A) True B) False Answer: A

16. Which of the following is superset to all ? A) Type 3 –regular grammar B) Type 2 –context free grammar C) Type 1 – context sensitive grammar D) Type 0 –unrestricted grammar Answer:D 17. Problems that can be solved in polynomial time are known as? A) Intractable B) Tractable C) Decision D) Complete Answer: B 18. -----------. is the class of decision problems that can be solved by non-deterministic polynomial algorithms? A) NP B) P C) Hard D) Complete Answer: A 19. -----------. is the class of decision problems that can be solved by deterministic polynomial algorithms? A) NP B) P C) Hard D) Complete Answer: B 20. Problems that cannot be solved by any algorithm are known as? A) Intractable B) Tractable C) Decision D) Complete Answer: A 21. The class P is the set of all decision problems that: A) Can be solved by polynomial-time algorithms. B) Can definitely not be solved by polynomial-time algorithms. C) Have polynomial-time algorithms that can verify potential solutions. D) All of the above. Answer: A 22. The class NP is the set of all decision problems that: A) Can be solved by polynomial-time algorithms. B) Can definitely not be solved by polynomial-time algorithms. C) Have polynomial-time algorithms that can verify potential solutions. D) All of the above. Answer: C 23. The class NP–complete is the set of all decision problems that: A) Can be solved by polynomial-time algorithms. B) Can definitely not be solved by polynomial-time algorithms.

C) Have polynomial-time algorithms that can verify potential solutions. D) None of the above. Answer: D 24. Suppose X p Y. Which must be true? A) Problem X is polynomial-time reducible to problem Y. B) Problem Y is polynomial-time reducible to problem X. C) Problems X and Y are polynomial-time equivalent. D) All of the above. Answer: A 25. Suppose X p Y. Which must be true? A) Problem X is polynomial-time reducible to problem Y. B) Problem Y is polynomial-time reducible to problem X. C) Problems X and Y are polynomial-time equivalent. D) All of the above. Answer: D 26. Suppose X p Y and Y p Z. Which must be true? A) Y p X. B) Z p Y. C) X p Z. D) All of the above. Answer: C 27. Suppose X p Y and Y p Z and Z p X. Which must be true? A) Y p X. B) Z p Y. C) X p Z. D) All of the above. Answer: D 28. Which of the following statements are currently known to be true? A) P  NP. B) NP  P. C) P  NP. D) All of the above. Answer: C 29. The most important unresolved question in computer science is: A) Does P = NP? B) Why does Windows crash so often? C) Why isn’t C++ named ++C, since we wish to use this language after the extra features were added to C? D) How many years will I need to work before my total career salary equals Bill Gates’ hourly income? E) Why aren’t there at least 5 or more algorithms courses in our undergraduate CS curriculum? Answer: A (now this problem is solved) 30. The Satisfiability, Clique, Independent Set, and Hamiltonian Cycle problems are known to be: A) Members of the class P. B) Members of the class NP–complete. C) Both of the above. D) None of the above. Answer: B

31. The Minimum Spanning Tree, Sorting, and Matrix Chain Multiplication problems are known to be: A) Members of the class P. B) Members of the class NP–complete. C) Both of the above. D) None of the above. Answer: A 32. The Graph Isomorphism and Prime Number problems are known to be: A) Members of the class P. B) Members of the class NP–complete. C) Both of the above. D) None of the above. Answer: D 33. Suppose problem X is in class P, problem Y is in class NP, and X p Y. Which must be true? A) Problem Y is in class P. B) Problem Y is NP–complete. C) Both of the above. D) None of the above. Answer: A 34. Suppose problem X is NP-complete, problem Y is in class NP, and X p Y. Which must be true? A) Problem Y is in class P. B) Problem Y is NP–complete. C) Both of the above. D) None of the above. Answer: B 35. Suppose problem X is in class P, problem Y is in class NP, and X p Y. Which must be true? A) Problem Y is in class P. B) Problem Y is NP–complete. C) Both of the above. D) None of the above. Answer: D 36. Suppose problem X is NP-complete, problem Y is in class NP, and X p Y. Which must be true? A) Problem Y is in class P. B) Problem Y is NP–complete. C) Both of the above. D) None of the above. Answer: B 37. Suppose problem X is in class NP, problem Y is in class P, and X p Y. Which must be true? A) Problem X is in class P. B) Problem X is NP–complete. C) Both of the above. D) None of the above. Answer: A

38. Suppose problem X is in class NP, problem Y is NP-complete, and X p Y. Which must be true? A) Problem X is in class P. B) Problem X is NP–complete. C) Both of the above. D) None of the above. Answer: D 39. Suppose problem X is NP-complete, problem Y is in class P, and X p Y. Which must be true? A) Problem X is in class P. B) Problem Y is NP–complete. C) P = NP. D) All of the above Answer: D 40. If you could prove, for some problem X, that problem X is NP-complete and also problem X is in class P, then: A) Dr. Borie would give you an A+ in CS 470 regardless of your grades on all these quizzes. B) You would be ready to write your dissertation and claim your PhD in computer science. C) You would receive job offers to join the computer science faculties at MIT and Stanford. D) The ACM would honor you with a Turing Award for your outstanding research contributions. E) All of the above. Answer: E GATE QUESTIONS WITH ANSWERS 1. Which of the following languages are undecidable? Note that ⟨M⟩⟨M⟩ indicates encoding of the Turing machine M. (GATE CS 2020) L1={⟨M⟩|L(M)=∅} L2={⟨M,w,q⟩|M on input w reaches state q in exactly 100 steps} L3={⟨M⟩|L(M)is not recursive} L4={⟨M⟩|L(M)containsatleast21members} (A) L1,L3,and L4only (B) L1andL3only (C) L2andL3only (D) L2,L3andL4only Answer (A) 2. Consider the following sets: (GATE CS 2019) S1. Set of all recursively enumerable languages over the alphabet {0,1} S2. Set of all syntactically valid C programs S3. Set of all languages over the alphabet {0,1} S4. Set of all non-regular languages over the alphabet {0,1} Which of the above sets are uncountable? (A) S1 and S2 (B) S3 and S4

(C) S2 and S3 (D) S1 and S4 Answer: (B) 3. Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turning machine M. (GATE CS 2017) Which of the following decision problems are undecidable? I. Given a regular expression R and a string ww, is w∈L(R)? II. Given context-free grammar G, is L(G)=ϕ ? III. Given a context-free grammar G, is L(G)=∑∗ for some alphabet ∑ ? IV. Given a Turning machine M and a string ww, is w∈L(M) ? (A) I and IV only (B) II and III only (C) II, III, and IV only (D) III and IV only Answer:(D) 4. Which of the following decision problems are undecidable? I. Given NFAs N1 and N2 is L(N1)∩L(N2) =Φ? II. Given a CFG G = (N,Σ,P,S) and a string x∈Σ∗, does x∈L∗(G)? III. Given CFGs G1 and G2, is L(G1) = L(G2)? IV. Given a TM M, is L(M)=Φ? (A) I and IV only (B) II and III only (C) III and IV only (D) II and IV only Answer (C). 5. For any two languages L1 and L2 such that L1 is context free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true? GATE CS 2015 1. L1' (complement of L1) is recursive 2. L2' (complement of L2) is recursive 3. L1' is context-free 4. L1' ∪ L2 is recursively enumerable (A) 1 only (B) 3 only (C) 3 and 4 only (D) 1and 4 only Answer (D) 6. Let be the encoding of a Turing machine as a string over ∑= {0, 1}. Let L = { |M is a Turing machine that accepts a string of length 2014 }. Then, L is GATE CS 2014 (A) Decidable and recursive enumerable (B) Undecidable and recursive enumerable (C) Undecidable and not recursive enumerable (D) Decidable but not recursive enumerable Answer (A)

7. Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility? GATE CS 2014 (A) Neither L nor L' is recursively enumerable (r.e.). (B) One of L and L' is r.e. but not recursive; the other is not r.e. (C) Both L and L' are r.e. but not recursive (D) Both L and L' are recursive Answer (C) 8. Which of the following problems are decidable? ….1) Does a given program ever produce an output? ….2) If L is a context-free language, then is L’ (complement of L) also context-free? ….3) If L is a regular language, then is L’ also regular? ….4) If L is a recursive language, then, is L’ also recursive? GATE CS 2012 (A) 1, 2, 3, 4 (B) 1, 2, (C) 2, 3, 4 (D) 3, 4 Answer (D) 9. Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true? GATE CS 2010 (A) L2 – L1 is recursively enumerable. (B) L1 – L3 is recursively enumberable (C) L2 ∩ L1 is recursively enumberable (D) L2 ∪ L1 is recursively enumberable Answer (B) 10. Match all items in Group 1 with correct options from those given in Group 2. GATE CS 2009 Group 1 Group2 P. Regular expression 1. Syntax analysis Q.Pushdown automata 2. Code generation R.Dataflow analysis 3. Lexical analysis S.Register allocation 4. Code optimization (A) P-4. Q-1, R-2, S-3 (B) P-3, Q-1, R-4, S-2 (C) P-3, Q-4, R-1, S-2 (D) P-2, Q-1, R-4, S-3 Answer (B)...