MCQOPTIONS
Saved Bookmarks
MCQOPTIONS
This section includes 20 Mcqs, each offering curated multiple-choice questions to sharpen your Computer Science knowledge and support exam preparation. Choose a topic below to get started.
| 1. |
Consider the following sets:S1. Set of all recursively enumerable languages over the alphabet {0,1}S2. Set of all syntactically valid C programsS3. 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» C. S2 and S3 | |
| 2. |
If L ϵ NP is a language such that L' ≤p L for some L' ϵ NPC, then: |
| A. | L is NP-Hard |
| B. | L is NP only |
| C. | L is NPC |
| D. | L is P only |
| Answer» C. L is NPC | |
| 3. |
Let A and B be finite alphabets and let # be a symbol outside both A and B. Let f be a total function from A* to B*. We say f is computable if there exists a Turing machine M which given an input x in A*. always halts with f(x) on its tape. Let Lf denote the language {x # f(x) |x ∈ A*}. Which of the following statements is true: |
| A. | f is computable if and only if Lf is recursive. |
| B. | f is computable if and only if Lf is recursively enumerable. |
| C. | If f is computable then Lf is recursive. But not conversely. |
| D. | If f is computable then Lf is recursively enumerable, but not conversely. |
| Answer» B. f is computable if and only if Lf is recursively enumerable. | |
| 4. |
If \( L\) and \(\bar L\) are recursively enumerable, then L is |
| A. | Regular |
| B. | Context-free |
| C. | Context-sensitive |
| D. | Recursive |
| Answer» E. | |
| 5. |
Consider the following languages.L1 = { | M takes at least 2016 steps on some input},L2 = { | M takes at least 2016 steps on all inputs} andL3 = { | M accepts ϵ},Where for each Turing machine M, denotes a specific encoding of M. Which one of the following is TRUE? |
| A. | L1 is recursive and L2, L3 are not recursive |
| B. | L2 is recursive and L1, L3 are not recursive |
| C. | L1, L2 are recursive and L3 is not recursive |
| D. | L1, L2, L3 are recursive |
| Answer» D. L1, L2, L3 are recursive | |
| 6. |
Let L1 be regular language, L2 be a deterministic context free language and L3 a recursively enumerable language, but not recursive. Which one of the following statements is false? |
| A. | L3∩L1 is recursive |
| B. | L1∩L2 ∩L3 is recursively enumerable |
| C. | L1 ∪ L2 is context free |
| D. | L1∩L2 is context free |
| Answer» B. L1∩L2 ∩L3 is recursively enumerable | |
| 7. |
Consider the following statements.I. The complement of every Turing decidable language is Turing decidableII. There exists some language which is in NP but is not Turing decidableIII. If L is a language in NP, L is Turing decidableWhich of the above statements is/are true? |
| A. | Only II |
| B. | Only III |
| C. | Only I and II |
| D. | Only I and III |
| Answer» E. | |
| 8. |
Language L1 is polynomial time reducible to language L2. Language L3 is polynomial time reducible to L2, which in turn is polynomial time reducible to language L4. Which of the following is/are true?I. if L4 ∈ P, then L2 ∈ PII. if L1 ∈ P or L3 ∈ P, then L2 ∈ PIII. L1 ∈ P, if and only if L3 ∈ PIV. if L4 ∈ P, then L1 ∈ P and L3 ∈ P |
| A. | II only |
| B. | III only |
| C. | I and IV only |
| D. | I only |
| Answer» D. I only | |
| 9. |
Consider the following two statements about regular languages:S1: Every infinite regular language contains an undecidable language as a subset.S2: Every finite language is regular.Which one of the following choices is correct? |
| A. | Only S2 is true. |
| B. | Neither S1 nor S2 is true. |
| C. | Only S1 is true. |
| D. | Both S1 and S2 are true. |
| Answer» E. | |
| 10. |
Let G1 and G2 be arbitrary context free languages and R an arbitrary regular language.Consider the following problems:(A) Is L(G1) = L(G2)?(B) Is L(G2) ≤ L(G1)?(C) Is L(G1) = R?Which of the problems are undecidable ?Choose the correct answer from the options given below: |
| A. | (A) only |
| B. | (B) only |
| C. | (A) and (B) only |
| D. | (A), (B) and (C) |
| Answer» E. | |
| 11. |
If L and P are two recursively enumerable languages, then they are not closed under |
| A. | Kleene Star L* of L |
| B. | Intersection \(L∩P\) |
| C. | Union \(L∪P\) |
| D. | Set difference |
| Answer» E. | |
| 12. |
Let X be a recursive language and Y be a recursively enumerable but not recursive language.Let W and Z be two languages such that Y̅ reduces to W, and Z reduces to X̅ (reduction means the standard many-one reduction). Which one of the following statements is TRUE? |
| A. | W can be recursively enumerable and Z is recursive. |
| B. | W can be recursive and Z is recursively enumerable. |
| C. | W is not recursively enumerable and Z is recursive. |
| D. | W is not recursively enumerable and Z is not recursive. |
| Answer» D. W is not recursively enumerable and Z is not recursive. | |
| 13. |
Let < M > be the encoding of a Turing machine as a string over ∑ = {0, 1}. Let L = { < M > | M is a Turing machine that accepts a string of length 2014 }. Then, L is |
| A. | decidable and recursively enumerable |
| B. | undecidable but recursively enumerable |
| C. | undecidable and not recursively enumerable |
| D. | decidable but not recursively enumerable |
| Answer» C. undecidable and not recursively enumerable | |
| 14. |
Consider the following problem X“Given a Turing Machine M over the input alphabet Σ any state q of M and word Σ*, does the computation of M on w visit the state q”Which of the following X is correct? |
| A. | X is undecidable but partially decidable |
| B. | X is undecidable but not even partially decidable |
| C. | X is decidable |
| D. | X is not a decision problem |
| Answer» B. X is undecidable but not even partially decidable | |
| 15. |
Given below are two statements:Statement I: The problem "Is L1 ∧ L2 = ϕ?" is undecidable for context sensitive languages L1 and L2.Statement II: The problem "Is WϵL?" is decidable for context sensitive language L, (where W is a string).In the light of the above statements, choose the correct answer from the options given below |
| A. | Both Statement I and Statement II are true |
| B. | Both Statement I and Statement II are false |
| C. | Statement I is correct but Statement II is false |
| D. | Statement I is incorrect but Statement II is true |
| Answer» B. Both Statement I and Statement II are false | |
| 16. |
Given the following statementsS1 : Every context-sensitive language L is recursiveS2 : There exists a recursive language that is not context-sensitiveWhich statements are true? |
| A. | Only S1 is correct |
| B. | Only S2 is correct |
| C. | Both S1 and S2 are not correct |
| D. | Both S1 and S2 are correct |
| Answer» E. | |
| 17. |
Consider the decision Problem 2CFSAT defined as follows:{ φ | φ is a satisfiable propositional formula in CNF with at most two literals per clause }For example, φ = (x1 v x2)⋀ (x1v x3̅ ) ⋀ (x2 v x4) is a Boolean formula and it is in 2 CNFSAT.The decision problem 2 CNFSAT is |
| A. | .NP complete |
| B. | .Solvable in polynomial time by reduction to directed graph reachability. |
| C. | .Solvable in constant time since any input instance is satisfiable. |
| D. | .NP-hard but not NP-complete |
| Answer» C. .Solvable in constant time since any input instance is satisfiable. | |
| 18. |
For a Turing machine M, {M} denotes an encoding of M. Consider the following two languages.L1 = {(M) | M takes more than 2021 steps on all inputs}L2 = {(M) | M takes more than 2021 steps on some input}Which one of the following options is correct? |
| A. | Both L1 and L2 are undecidable. |
| B. | L1 is undecidable and L2 is decidable. |
| C. | L1 is decidable and L2 is undecidable. |
| D. | Both L1 and L2 are decidable. |
| Answer» E. | |
| 19. |
Let L be a language and \(\vec L\) be its complement. Which one of the following is NOT a viable possibility? |
| A. | Neither L nor \(\vec L\) is recursively enumerable (r.e.). |
| B. | One of L and \(\vec L\) is r.e. but not recursive; the other is not r.e. |
| C. | Both L and \(\vec L\) are r.e. but not recursive. |
| D. | Both L and \(\vec L\) are recursive. |
| Answer» D. Both L and \(\vec L\) are recursive. | |
| 20. |
Let L = {ap |p is a prime}. Then which of the following is true |
| A. | It is not accepted by a Turing Machine |
| B. | It is regular but not context free |
| C. | It is context free but not regular |
| D. | It is neither regular nor context free, but accepted by a Turing Machine |
| Answer» E. | |