| 1. | 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 | |
| 2. | 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 | |
| 3. | 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 | |
| 4. | 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 | |
| 5. | 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» A. 1, 2 and 3 | |
| 6. | 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 | |
| 7. | 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 | |
| 8. | 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 | |
| 9. | 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 | |
| 10. | 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 | |
| 11. | 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 | |
| 12. | 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 | |
| 13. | 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 | |
| 14. | 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 ∑ | |
| 15. | 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 | |
| 16. | 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 | |
| 17. | 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 | |
| 18. | 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 | |
| 19. | 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 | |
| 20. | 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, | |
| 21. | Recursively enumerable languages are not closed under: |
| A. | Union |
| B. | Intersection |
| C. | Complementation |
| D. | Concatenation |
| Answer» C. Complementation | |
| 22. | 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 | |
| 23. | 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 | |
| 24. | 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 | |
| 26. | 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. | |
| 27. | Recursively enumerable languages are not closed under |
| A. | Complementation |
| B. | Union |
| C. | Intersection |
| D. | None of the above |
| Answer» A. Complementation | |
| 28. | The following CFG is in S → aBB B → bAA A → a B → 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» D. Greibach normal form | |
| 29. | 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 | |
| 30. | 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 | |
| 31. | 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 | |
| 32. | ___________ 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 | |
| 33. | 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 | |
| 34. | 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 | |
| 35. | 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 | |
| 36. | 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 | |
| 37. | 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 | |
| 38. | 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 | |
| 39. | 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 | |
| 40. | 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 | |
| 41. | 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. | |
| 42. | 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) | |
| 43. | Which of the following will be used for text searching application-? |
| A. | NFA |
| B. | DFA |
| C. | PDA |
| D. | None of these |
| Answer» C. PDA | |
| 44. | 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) | |
| 45. | 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) | |
| 46. | 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 | |
| 47. | 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)} | |
Tags
Question and answers in Unit 4,Unit 4 Multiple choice questions and answers,Unit 4 Important MCQs,Solved MCQs for Unit 4,Unit 4 MCQs with answers PDF download
