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