McqMate
Chapters
1. |
Suppose that a problem A is known to have a polynomial-time verification algorithm. Which of the following statements can be deduced. |
A. | A is in NP. |
B. | A is in NP but not P |
C. | A is in both NP and P. |
D. | A is NP-complete. |
Answer» B. A is in NP but not P |
2. |
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» C. Both False |
3. |
A PC not connected to a network is equivalent to |
A. | A Deterministic Finite-State Automaton, |
B. | A Turing Machine, |
C. | A Push-Down Automaton, |
D. | None of the above. |
Answer» A. A Deterministic Finite-State Automaton, |
4. |
Recursively enumerable languages are not closed under: |
A. | Union |
B. | Intersection |
C. | Complementation |
D. | Concatenation |
Answer» C. Complementation |
5. |
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» B. (L1)’ is recursive and (L2)’ is not recursively enumerable |
6. |
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 |
Answer» A. R is NP-complete |
7. |
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 |
Answer» D. L is regular |
8. |
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 |
Answer» A. Turing machine |
9. |
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. |
Answer» C. Any regular languages have an equivalent CFG. |
10. |
Recursively enumerable languages are not closed under |
A. | Complementation |
B. | Union |
C. | Intersection |
D. | None of the above |
Answer» A. Complementation |
11. |
The following CFG is in
|
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 |
12. |
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 |
Answer» A. PALINDROME and PRIME |
13. |
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» B. Pumping Lemma |
14. |
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 |
Answer» A. True |
15. |
___________ states are called the halt states. |
A. | ACCEPT and REJECT |
B. | ACCEPT and READ |
C. | ACCEPT AND START |
D. | ACCEPT AND WRITE |
Answer» A. ACCEPT and REJECT |
16. |
The part of an FA, where the input string is placed before it is run, is called _______ |
A. | State |
B. | Transition |
C. | Input Tape |
D. | Output Tape |
Answer» C. Input Tape |
17. |
The PDA is called non-deterministic PDA when there are more than one out going edges from……… state |
A. | START or READ |
B. | POP or REJECT |
C. | READ or POP |
D. | PUSH or POP |
Answer» C. READ or POP |
18. |
If an effectively solvable problem has answered in yes or no, then this solution is called |
A. | Decision procedure |
B. | Decision method |
C. | Decision problem |
D. | Decision making |
Answer» A. Decision procedure |
19. |
The symbols that can’t be replaced by anything are called ----------------- |
A. | Productions |
B. | Terminals |
C. | Non-terminals |
D. | All of above |
Answer» B. Terminals |
20. |
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» D. Terminals and non-terminals |
21. |
Choose the incorrect statement: |
A. | (a+b)aa(a+b)generates Regular language. |
B. | A language consisting of all strings over ∑={a,b} having equal number of a’s and b’s is a regular language |
C. | Every language that can be expressed by FA can also be expressed by RE |
D. | None of these |
Answer» D. None of these |
22. |
Choose the incorrect statement. |
A. | A Mealy machine generates no language as such |
B. | A Mealy machine has no terminal state |
C. | For a given input string, length of the output string generated by a Moore machine is not more than the length of the output string generated by that of a Mealy machine |
D. | All of these |
Answer» C. For a given input string, length of the output string generated by a Moore machine is not more than the length of the output string generated by that of a Mealy machine |
23. |
In FA, if one enters in a specific state but there is no way to leave it, then that specific state is called |
A. | Dead State |
B. | Waste Basket |
C. | Davey John Locker |
D. | All of these |
Answer» D. All of these |
24. |
Which statement is true? |
A. | The tape of turing machine is infinite. |
B. | The tape of turing machine is finite. |
C. | The tape of turing machine is infinite when the language is regular |
D. | The tape of turing machine is finite when the language is nonregular. |
Answer» A. The tape of turing machine is infinite. |
25. |
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» A. (r1)(r2) |
26. |
Which of the following will be used for text searching application-? |
A. | NFA |
B. | DFA |
C. | PDA |
D. | None of these |
Answer» C. PDA |
27. |
Context free grammar is used for- |
A. | Lexical analyzer |
B. | Document type definition (DTD) |
C. | Text pattern searching |
D. | Both a & c |
Answer» B. Document type definition (DTD) |
28. |
The set strings of 0's and 1's with atmost one pair consecutive one's- |
A. | (0+1)*(01)(10)(0+1)* |
B. | (0+1)*(01)*(10)(0+1)* |
C. | (0+1)*(01)(10)*(0+1)* |
D. | (0+!)(01)*(10)*(0+1) |
Answer» D. (0+!)(01)*(10)*(0+1) |
29. |
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» C. NP-complete and in P respectively |
30. |
Which of the following instances of the post correspondence problem has a viable sequence (a solution)? |
A. | {(b, bb), (bb, bab), (bab, abb), (abb, babb)} |
B. | {(ab, aba), (baa, aa), (aba, baa)} |
C. | {(ab, abb), (ba, aaa), (aa, a)} |
D. | none of the above |
Answer» C. {(ab, abb), (ba, aaa), (aa, a)} |
31. |
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» A. Both FHAM and DHAM are NP-hard |
32. |
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» C. P3 is NP complete if P2 is reducible to P3 |
33. |
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» D. L is a regular set |
34. |
Which one of the following is not decidable? |
A. | given a Turing machine M, a string s, and an integer k, M accepts s with k steps |
B. | equivalence of two given Turing machines |
C. | language accepted by a given DFSA is nonempty |
D. | language generated by a CFG is nonempty |
Answer» B. equivalence of two given Turing machines |
35. |
Which of the following statements are TRUE?
|
A. | 1, 2 and 3 |
B. | 1 and 2 only |
C. | 2 and 3 only |
D. | 1 and 3 only |
Answer» A. 1, 2 and 3 |
36. |
Consider a graph G = (V, E) where I V I is divisible by 3. The problem of finding a Hamiltonian cycle in a graph is denoted by SHAM3 and the problem of determining if a Hamiltonian cycle exits in such graph is denoted by DHAM3. The option, which holds true, is |
A. | Only DHAM3 is NP-hard |
B. | Only SHAM3 is NP-hard |
C. | Both SHAM3 and DHAM3 are NP-hard |
D. | Neither SHAM3 nor DHAM3 is NP-hard |
Answer» C. Both SHAM3 and DHAM3 are NP-hard |
37. |
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» D. Turing recognizable languages are closed under union and complementation |
38. |
Two persons X and Y have been asked to show that a certain problem p is NP-complete. X shows a polynomial time reduction from the 3-SAT problem to p and Y shows a polynomial time reduction from p to 3-SAT. From these reduction it can be inferred that |
A. | P is NP-complete |
B. | P is NP-hard but not NP-complete |
C. | P is in NP but not NP-complete |
D. | P is neither NP-hard nor in NP |
Answer» A. P is NP-complete |
39. |
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» A. NP-complete and in P respectively |
40. |
Let n be the positive integer constant and L be the language with alphabet {a}. To recognize L the minimum number of states required in a DFA will be |
A. | 2k + 1 |
B. | k + 1 |
C. | 2n + 1 |
D. | n + 1 |
Answer» D. n + 1 |
41. |
Consider a stack, which is limited to 10 items. The language accepted by a push- down automaton in such stack is best described as |
A. | Regular |
B. | Deterministic context free |
C. | Context free |
D. | Recursive |
Answer» A. Regular |
42. |
State table of an FSM is given below. There are two states A And B, one input and one output. Let the initial state be A = 0 and B = 0. To take the machine to the state A = 0 and B = 1 with output = 1 the minimum length of input string required will be |
A. | 2 |
B. | 7 |
C. | 4 |
D. | 3 |
Answer» D. 3 |
43. |
Out of the three decision problems P1, P2 and P3, P1 is decidable and P2 is undecidable. The statement that holds true is |
A. | P3 is decidable if P3 is reducible to compliment of P2 |
B. | P3 is decidable if P1 is reducible to P3 |
C. | P3 is undecidable if P1 is reducible to P3 |
D. | P3 is undecidable if P2 is reducible to P3 |
Answer» D. P3 is undecidable if P2 is reducible to P3 |
44. |
The set which is not countable if we have ∑ = {a, b}, is |
A. | Set of all languages over ∑ accepted by turing machine |
B. | Set of all regular languages over ∑ |
C. | Set of all strings over ∑ |
D. | Set of all languages over ∑ |
Answer» D. Set of all languages over ∑ |
45. |
How many states are present in the minimum state finite automaton that recognizes the language represented by the regular expression (0+1)(0+1)…..N times? |
A. | n+1 |
B. | n+2 |
C. | n |
D. | 2n |
Answer» B. n+2 |
46. |
Consider the state table of a finite state machine that has input x and a single output z. The shortest input sequence to reach the final state C if the initial state is unknown is |
A. | 10 |
B. | 01 |
C. | 101 |
D. | 110 |
Answer» A. 10 |
47. |
The set that can be recognized by a deterministic finite state automaton is |
A. | The set {1, 101, 11011, 1110111, …….} |
B. | The set of binary string in which the number of 0’s is same as the number of1’s |
C. | 1, 2, 4, 8……2n ….. written in binary |
D. | 1, 2, 4, 8……2n ….. written in unary |
Answer» C. 1, 2, 4, 8……2n ….. written in binary |
Done Reading?