MCQOPTIONS
Saved Bookmarks
MCQOPTIONS
This section includes 151 Mcqs, each offering curated multiple-choice questions to sharpen your Computer Science knowledge and support exam preparation. Choose a topic below to get started.
| 51. |
Which of the following is true with respect to Kleene’s theorem?1 A regular language is accepted by a finite automaton.2 Every language is accepted by a finite automaton or a turingmachine. |
| A. | 1 only |
| B. | 2 only |
| C. | Both 1 and 2 are true statements |
| D. | None is true |
| Answer» D. None is true | |
| 52. |
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 |
| Answer» C. (L1)’ and (L2)’ are recursively enumerable | |
| 53. |
If an effectively solvable problem has answered in yes or no, then thissolution is called |
| A. | Decision procedure |
| B. | Decision method |
| C. | Decision problem |
| D. | Decision making |
| Answer» B. Decision method | |
| 54. |
If a language is denoted by a regular expression L = ( x )* (x y x ), then which of the following is not a legal string within L ? |
| A. | yx |
| B. | xyx |
| C. | x |
| D. | xyxyx |
| Answer» E. | |
| 55. |
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 |
| Answer» C. Kleene’s theorem | |
| 56. |
The regular sets are closed under: |
| A. | Union |
| B. | Concatenation |
| C. | Kleene closure |
| D. | All of the above |
| Answer» E. | |
| 57. |
Given S = {a, b}, which one of the following sets is not countable? |
| A. | the set all strings over Σ |
| B. | the set of all language over Σ |
| C. | the set of all binary strings |
| D. | the set of all languages over Σ accepted by turing machines |
| Answer» C. the set of all binary strings | |
| 58. |
Which of the following statements are TRUE?(1) The problem of determining whether there exists a cycle in an undirected graph is in P.(2) The problem of determining whether there exists a cycle in an undirected graph is in NP.(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A. |
| A. | 1, 2 and 3 |
| B. | 1 and 2 only |
| C. | 2 and 3 only |
| D. | 1 and 3 only |
| Answer» B. 1 and 2 only | |
| 59. |
Consider the regular language L = (111+111111)*. The minimum number ofstates inany DFA accepting this language is |
| A. | 3 |
| B. | 5 |
| C. | 8 |
| D. | 9 |
| Answer» E. | |
| 60. |
Consider the regular language L =(111+11111)*. The minimum number of states in any DFA accepting this languages is: |
| A. | 3 |
| B. | 5 |
| C. | 8 |
| D. | 9 |
| Answer» E. | |
| 61. |
Type-1 Grammar is known as_____________ |
| A. | CFG |
| B. | CSG |
| C. | REGULAR |
| D. | All |
| Answer» C. REGULAR | |
| 62. |
Four pairs are following; in each pair both objects have some common thing. Choose the odd pair; |
| A. | (tm, 2pda) |
| B. | (computer, utm) |
| C. | (2pda, npda) |
| D. | (fa, pda) |
| Answer» E. | |
| 63. |
The following grammarG = (N, T, P, S)N = {S, A, B, C}T = {a, b, c}P : S → aSA → bBB → cCC → a is |
| A. | is type 3 |
| B. | is type 2 but not type 3 |
| C. | is type 1 but not type 2 |
| D. | is type 0 but not type 1 |
| Answer» B. is type 2 but not type 3 | |
| 64. |
Consider the following statements about the context free grammar G = {S - >SS,S - >ab,S ->ba, S - ε}I. G is ambiguousII. G produces all strings with equal number of a’s and b’sIII. G can be accepted by a deterministic PDA.Which combination below expresses all the true statements about G? |
| A. | 1 only |
| B. | 1 and 3 |
| C. | 2 and 3 |
| D. | 1,2 and 3 |
| Answer» E. | |
| 65. |
PCP is: |
| A. | Decidable |
| B. | Undecidable |
| C. | Sometimes Decidable |
| D. | None of the |
| Answer» C. Sometimes Decidable | |
| 66. |
___________ states are called the halt states. |
| A. | ACCEPT and REJECT |
| B. | ACCEPT and READ |
| C. | ACCEPT AND START |
| D. | ACCEPT AND WRITE |
| Answer» B. ACCEPT and READ | |
| 67. |
Match all items in Group 1 with correct options from those given in Group 2.List I List II**spaceP. Regular Expression 1. Syntax analysis**spaceQ. Push down automata 2. Code Generation**spaceR. Dataflow analysis 3. Lexical analysis**spaceS. 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» C. P-3, Q-4, R-1, S-2 | |
| 68. |
If r1 = (aa + bb) and r2 = (a + b) then the language (aa + bb)(a + b) will be generated by Select correct option: |
| A. | (r1)(r2) |
| B. | (r1 + r2) |
| C. | (r2)(r1) |
| D. | (r1) |
| Answer» B. (r1 + r2) | |
| 69. |
Two strings x and y are indistinguishable if: |
| A. | δ*(s, x) = δ* (s, y), i.e. the state reached by a DFA M on input x is the same as the state reached by M on input y |
| B. | if for every string z Є ∑* either both xz and yz are in language A on ∑* or both xz and yz are not in A |
| C. | Both above statements are true |
| D. | None of the above |
| Answer» D. None of the above | |
| 70. |
The following CFG is inS → AB**spaceB → CD**spaceB → AD**spaceB → b**spaceD → AD**spaceD → d**spaceA → a**spaceC → a |
| 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 |
| Answer» D. Greibach normal form | |
| 71. |
The problem 3-SAT and 2-SAT are |
| A. | Both in P |
| B. | Both NP complete |
| C. | NP-complete and in P respectively |
| D. | Undecidable and NP-complete respectively |
| Answer» D. Undecidable and NP-complete respectively | |
| 72. |
Basic limitation of FSM is that it |
| A. | Cannot remember arbitrary large amount of information |
| B. | Sometimes fails to recognize grammars that are regular |
| C. | Sometimes recognizes grammars are not regular |
| D. | None of these |
| Answer» B. Sometimes fails to recognize grammars that are regular | |
| 73. |
Which of the following are regular sets? |
| A. | I and IV only |
| B. | I and III only |
| C. | I only |
| D. | IV only |
| Answer» B. I and III only | |
| 74. |
Any Language generated by an unrestricted grammar is: |
| A. | Recursive |
| B. | Recursively Enumerable |
| C. | Not Recursive |
| D. | None of the above |
| Answer» B. Recursively Enumerable | |
| 75. |
Which of the following statement is false for a turing machine? |
| A. | There exists an equivalent deterministic turing machine for every nondeterministic turing machine |
| B. | Turing decidable languages are closed under intersection and complementation |
| C. | Turing recognizable languages are closed under union and intersection |
| D. | Turing recognizable languages are closed under union and complementation |
| Answer» E. | |
| 76. |
Regular expressions are |
| A. | Type 0 language |
| B. | Type 1 language |
| C. | Type 2 language |
| D. | Type 3 language |
| Answer» B. Type 1 language | |
| 77. |
Which of the following will be used for text searching application-? |
| A. | NFA |
| B. | DFA |
| C. | PDA |
| D. | None of these |
| Answer» D. None of these | |
| 78. |
Consider three problems P1, P2 and P3. It is known that P1 has polynomial time solution and P2 is NP-complete and P3 is in NP. Which one of the following is true. |
| A. | P3 has polynomial time solution if P1 is polynomial time reducible to P3 |
| B. | P3 is NP complete if P3 is polynomial time reducible to P2 |
| C. | P3 is NP complete if P2 is reducible to P3 |
| D. | P3 has polynomial time complexity and P3 is reducible to P2 |
| Answer» D. P3 has polynomial time complexity and P3 is reducible to P2 | |
| 79. |
Context free grammar is used for- |
| A. | Lexical analyzer |
| B. | Document type definition (DTD) |
| C. | Text pattern searching |
| D. | Both a & c |
| Answer» C. Text pattern searching | |
| 80. |
Let FHAM be the problem of finding a Hamiltonian cycle in a graph G and DHAM be the problem of determining if a Hamiltonial cycle exists in a graph. Which one of the following is TRUE? |
| A. | Both FHAM and DHAM are NP-hard |
| B. | FHAM is NP hard, but DHAM is not |
| C. | DHAM is NP hard, but FHAM is not |
| D. | Neither FHAM nor DHAM is NP hard |
| Answer» B. FHAM is NP hard, but DHAM is not | |
| 81. |
Left hand side of a production in CFG consists of: |
| A. | One terminal |
| B. | More than one terminal |
| C. | One non-terminal |
| D. | Terminals and non-terminals |
| Answer» E. | |
| 82. |
How many strings of length less than 4 contains the language described bythe regular expression (x+y)*y(a+ab)*? |
| A. | 7 |
| B. | 10 |
| C. | 12 |
| D. | 11 |
| Answer» E. | |
| 83. |
The regular expression have all strings in which any number of 0’s is followed by any number of 1’s followed by any number of 2’s is : |
| A. | (0+1+2)* |
| B. | 0*1*2* |
| C. | 0* + 1 + 2 |
| D. | (0+1)*2* |
| Answer» C. 0* + 1 + 2 | |
| 84. |
Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression |
| A. | b*ab*ab*ab |
| B. | (a+b)* |
| C. | b*a(a+b)* |
| D. | b*ab*ab |
| Answer» D. b*ab*ab | |
| 85. |
A spanning tree for a simple graph of order 24 has |
| A. | 12 edges |
| B. | 6 edges |
| C. | 23 edges |
| D. | None of above. |
| Answer» D. None of above. | |
| 86. |
Let L denotes the language generated by the grammar S – OSO/00. Which of thefollowing is true? |
| A. | L = O |
| B. | L is regular but not O |
| C. | L is context free but not regular |
| D. | L is not context free |
| Answer» C. L is context free but not regular | |
| 87. |
The following CFG is inS → aBBB → bAAA → aB → 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 |
| Answer» E. | |
| 88. |
Which of the following assertions about Turing Machines is true? Blank symbol(s) may occur in the input. At any stage of a computation, there are only finitely many non-blank Symbols on the tape. |
| A. | Assertions (a) and (b) are both true. |
| B. | Neither (a) nor (b) is true. |
| C. | Both False |
| D. | None of above |
| Answer» D. None of above | |
| 89. |
A pushdown automata behaves like a Turing machine, when it has number of auxiliary/ memory. |
| A. | 0 |
| B. | exectly 2 |
| C. | 2 or more |
| D. | both exectly 2 or more are correct |
| Answer» D. both exectly 2 or more are correct | |
| 90. |
P, Q, R are three languages. If P & R are regular and if PQ=R, then |
| A. | Q has to be regular |
| B. | Q cannot be regular |
| C. | Q need not be regular |
| D. | Q has to be a CFL |
| Answer» D. Q has to be a CFL | |
| 91. |
The following grammarG = (N, T, P, S)**spaceN = {S, A, B, C, D, E}**spaceT = {a, b, c}**spaceP : S → aAB**spaceAB → CD**spaceCD → CE**spaceC → aC**spaceC → b**spacebE → bc is |
| A. | is type 3 |
| B. | is type 2 but not type 3 |
| C. | is type 1 but not type 2 |
| D. | is type 0 but not type 1 |
| Answer» D. is type 0 but not type 1 | |
| 92. |
Given a Non-deterministic Finite Automation (NFA) with states p and r as initial and final states respectively and transition table as given below:A BP - Qq R Sr R Ss R SThe minimum number of states required in Deterministic Finite Automation(DFA) equivalent to NFA is |
| A. | 5 |
| B. | 4 |
| C. | 3 |
| D. | 2 |
| Answer» D. 2 | |
| 93. |
Universal Turing machine (UTM) influenced the concepts of |
| A. | computability |
| B. | interpretive implementation of programming language |
| C. | program and data is in same memory |
| D. | all are correct |
| Answer» E. | |
| 94. |
Which one of the following statement is true for a regular language L over {a} whose minimal finite state automation has two states? |
| A. | L must be either {an I n is odd} or {an I n is even} |
| B. | L must be {an I n is odd} |
| C. | L must be {an I n is even} |
| D. | L must be {an I n = 0} |
| Answer» B. L must be {an I n is odd} | |
| 95. |
The symbols that can’t be replaced by anything are called ----------------- |
| A. | Productions |
| B. | Terminals |
| C. | Non-terminals |
| D. | All of above |
| Answer» C. Non-terminals | |
| 96. |
3-SAT and 2-SAT problems are |
| A. | NP-complete and in P respectively |
| B. | Undecidable and NP-complete |
| C. | Both NP-complete |
| D. | Both in P |
| Answer» B. Undecidable and NP-complete | |
| 97. |
Consider a language L for which there exists a Turing machine ™, T, that accepts every word in L and either rejects or loops for every word that is not in L. The language L is |
| A. | NP hard |
| B. | NP complete |
| C. | Recursive |
| D. | Recursively enumerable |
| Answer» E. | |
| 98. |
In which of the stated below is the following statement true?“For every non-deterministic machine M1, there exists as equivalent deterministic machine M2 recognizing the same language.” |
| A. | m1 is a non-deterministic finite automata |
| B. | m1 is a non-deterministic push-down automata |
| C. | m1 is a non-deterministic turing machine |
| D. | for no machine m1 use the above statement true |
| Answer» D. for no machine m1 use the above statement true | |
| 99. |
Which one of the following is the strongest correct statement about a finite language Lover a finite alphabet Σ? |
| A. | L is undecidable |
| B. | L is recursive |
| C. | L is a CSL |
| D. | L is a regular set |
| Answer» E. | |
| 100. |
Consider the following statementsI. Recursive languages are closed under complementationII. Recursively enumerable languages are closed under unionIII. Recursively enumerable languages are closed under complementationWhich of the above statement are TRUE? |
| A. | I only |
| B. | I and II |
| C. | I and III |
| D. | II and III |
| Answer» C. I and III | |