McqMate
These multiple-choice questions (MCQs) are designed to enhance your knowledge and understanding in the following areas: Computer Science Engineering (CSE) , Master of Computer Applications (MCA) .
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 Studing? Take A Test.
Great job completing your study session! Now it's time to put your knowledge to the test. Challenge yourself, see how much you've learned, and identify areas for improvement. Don’t worry, this is all part of the journey to mastery. Ready for the next step? Take a quiz to solidify what you've just studied.