Quiznetik

Theory of Computation | Set 2

1. Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

Correct : A. Both DHAM3 and SHAM3 are NP-hard

2. Consider the following statements about the context free grammar G = {S - >SS,S - >ab,S ->ba, S - ε} I. G is ambiguous II. G produces all strings with equal number of a’s and b’s III. G can be accepted by a deterministic PDA. Which combination below expresses all the true statements about G?

Correct : D. 1,2 and 3

3. Consider the regular language L =(111+11111)*. The minimum number of states in any DFA accepting this languages is:

Correct : D. 9

4. Give a production grammar for the language L = {x/x ∈ (a,b)*, the number of a’s in x is multiple of 3}.

Correct : A. {S->bS,S->b,S->aA,S->bA,A->aB,B->bB,B->aS,S->a}

5. The production Grammar is {S->aSbb,S->abb} is

Correct : B. type-2 grammar

6. Regular expression (x/y)(x/y) denotes the set

Correct : B. {xx,xy,yx,yy}

7. 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 :

Correct : B. 0*1*2*

8. Suppose that a problem A is known to have a polynomial-time verification algorithm. Which of the following statements can be deduced.

Correct : B. A is in NP but not P

9. 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.

Correct : C. Both False

10. A PC not connected to a network is equivalent to

Correct : A. A Deterministic Finite-State Automaton,

11. Recursively enumerable languages are not closed under:

Correct : C. Complementation

12. 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?

Correct : B. (L1)’ is recursive and (L2)’ is not recursively enumerable

13. 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?

Correct : A. R is NP-complete

14. 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?

Correct : D. L is regular

15. A FSM can be considered, having finite tape length without rewinding capability and unidirectional tape movement

Correct : A. Turing machine

16. Which of the following statement is true?

Correct : C. Any regular languages have an equivalent CFG.

17. Recursively enumerable languages are not closed under

Correct : A. Complementation

18. The following CFG is in S → aBB B → bAA A → a B → b

Correct : D. Greibach normal form

19. The languages -------------- are the examples of non regular languages.

Correct : A. PALINDROME and PRIME

20. 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

Correct : B. Pumping Lemma

21. Languages are proved to be regular or non regular using pumping lemma.

Correct : A. True

22. ___________ states are called the halt states.

Correct : A. ACCEPT and REJECT

23. The part of an FA, where the input string is placed before it is run, is called _______

Correct : C. Input Tape

24. The PDA is called non-deterministic PDA when there are more than one out going edges from……… state

Correct : C. READ or POP

25. If an effectively solvable problem has answered in yes or no, then this solution is called

Correct : A. Decision procedure

26. The symbols that can’t be replaced by anything are called -----------------

Correct : B. Terminals

27. Left hand side of a production in CFG consists of:

Correct : D. Terminals and non-terminals

28. Choose the incorrect statement:

Correct : D. None of these

29. Choose the incorrect statement.

Correct : 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

30. In FA, if one enters in a specific state but there is no way to leave it, then that specific state is called

Correct : D. All of these

31. Which statement is true?

Correct : A. The tape of turing machine is infinite.

32. If r1 = (aa + bb) and r2 = (a + b) then the language (aa + bb)(a + b) will be generated by Select correct option:

Correct : A. (r1)(r2)

33. Which of the following will be used for text searching application-?

Correct : C. PDA

34. Context free grammar is used for-

Correct : B. Document type definition (DTD)

35. The set strings of 0's and 1's with atmost one pair consecutive one's-

Correct : D. (0+!)(01)*(10)*(0+1)

36. The problem 3-SAT and 2-SAT are

Correct : C. NP-complete and in P respectively

37. Which of the following instances of the post correspondence problem has a viable sequence (a solution)?

Correct : C. {(ab, abb), (ba, aaa), (aa, a)}

38. 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?

Correct : A. Both FHAM and DHAM are NP-hard

39. 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.

Correct : C. P3 is NP complete if P2 is reducible to P3

40. Which one of the following is the strongest correct statement about a finite language Lover a finite alphabet Σ?

Correct : D. L is a regular set

41. Which one of the following is not decidable?

Correct : B. equivalence of two given Turing machines

42. 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.

Correct : A. 1, 2 and 3

43. 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

Correct : C. Both SHAM3 and DHAM3 are NP-hard

44. Which of the following statement is false for a turing machine?

Correct : D. Turing recognizable languages are closed under union and complementation

45. 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

Correct : A. P is NP-complete

46. 3-SAT and 2-SAT problems are

Correct : A. NP-complete and in P respectively

47. 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

Correct : D. n + 1

48. Consider a stack, which is limited to 10 items. The language accepted by a push- down automaton in such stack is best described as

Correct : A. Regular

49. 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

Correct : D. 3

50. Out of the three decision problems P1, P2 and P3, P1 is decidable and P2 is undecidable. The statement that holds true is

Correct : D. P3 is undecidable if P2 is reducible to P3

51. The set which is not countable if we have ∑ = {a, b}, is

Correct : D. Set of all languages over ∑

52. 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?

Correct : B. n+2

53. 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

Correct : A. 10

54. The set that can be recognized by a deterministic finite state automaton is

Correct : C. 1, 2, 4, 8……2n ….. written in binary

55. What is the reason behind a Turing machine is more powerful than finite state machine FSM?

Correct : C. turing machine has capability remember arbitrary long sequence of input string.

56. A pushdown automata behaves like a Turing machine, when it has number of auxiliary/ memory.

Correct : C. 2 or more

57. The language L = {anbnan n≥ 1} is recognized by

Correct : D. all are correct

58. If Turing machine accepts all the words of the languages L and rejects or loops for other words, which are not in L, then L is said to be

Correct : A. recursive enumerable

59. If a Turing machine halts for each and every world of a language L and rejects other, then L is said to be

Correct : C. context free language

60. Universal Turing machine (UTM) influenced the concepts of

Correct : D. all are correct

61. The number of symbols necessary to simulate a Turing machine with m symbols and n states

Correct : A. 4m × n + m

62. A universal Turing machine is a

Correct : A. reprogrammable truing machine

63. He difference between a read-only Turing machine and a two-way finite state machine is

Correct : C. storage capacity

64. Which is correct regard an off-line Truing machine?

Correct : A. an offline turing machine is a special type of multi-tape turing machine

65. Which of the following statement is wrong?

Correct : D. power of ntm and tm is not same

66. Four pairs are following; in each pair both objects have some common thing. Choose the odd pair;

Correct : D. (fa, pda)

67. We think of a Turing machine’s transition function as a

Correct : B. software

68. Church’s Thesis supports

Correct : C. both tm is an general-purpose computer and tm is an algorithm and vice-versa are correct

69. A random access machine (RAM) and truing machine are different in

Correct : D. both accessing and storage are correct

70. Choose the correct statement

Correct : D. both recursive set ⊆ recursive enumerable set and recursive sets are analogous to total functions are correct.

71. Given S = {a, b}, which one of the following sets is not countable?

Correct : B. the set of all language over Σ

72. 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.”

Correct : C. m1 is a non-deterministic turing machine

73. Which of the following conversion is not possible (algorithmically)?

Correct : B. non-deterministic finite state automata to deterministic finite state automata