1. S -> aAB, AB -> bB, B -> b, A -> aB satisfies ___________ type of grammar
Correct : C. 0,1
2. If there are more than 2 LMD for a string then it is said to be ___________.
Correct : A. Ambigious
3. A finite non-empty set of symbols is called _________.
Correct : A. alphabet
4. The specification of proper construction of a sentence is called ______.
Correct : C. syntax
5. Context free grammar is also known as _______ grammar.
Correct : C. type 2
6. A class of machine which accepts a ________ language is called finite state automata.
Correct : D. type 3
7. Accepting states are denoted by ________.
Correct : C. double circle
8. For converting NDFA to DFA we should __________ all the states which have no
incoming.
Correct : D. delete
9. The set of all finite words over E is denoted by ________.
Correct : A. E+
10. Surjective function is also called ________.
Correct : A. onto
11. One to one onto function is also called __________.
Correct : A. bijective
12. The composition of function is associative but not _______.
Correct : A. commutative
13. A mapping x into itself is called __________.
Correct : A. reflexive
14. The duality law of (P^Q)vT is ________.
Correct : D. (PvQ)^F
15. A sum of the variables and their negations in a formula is called _________.
Correct : A. elementary sum
16. A premise may be introduced at any point in the derivation is called ________.
Correct : A. Rule P
17. A product of the variables and their negations in a formula is called _________.
Correct : A. elementary product
18. Min-terms of two statements are formed by introducing the connective _________.
Correct : A. Conjunction
19. Any vertex having degree one is called _______.
Correct : B. pendent vertex
20. A graph that has neither self loops nor parallel edges is called_____graph.
Correct : B. simple
21. A graph in which every vertex has same degree is called _________graph.
Correct : A. regular
22. Kn denotes _______graph.
Correct : C. complete
23. The number of vertices of odd degree in a graph is always________.
Correct : B. even
24. A path of a graph is said to be ______ if it contains all the edges of the graph.
Correct : A. eulerian
25. Traveling salesman problem is example for_______graph.
Correct : B. hamiltonian
26. If a node v is reachable from node u then the path of minimum length u to v is called _____.
Correct : C. geodesic
27. The eccentricity of a center in a tree is defined as ______ of the tree.
Correct : A. radius
28. P -> Q , Q ->R then________.
Correct : A. P -> R
29. If a normal form contains all minterms, then it is ________.
Correct : A. a tautology
30. PCNF is also called _______.
Correct : B. product of sum canonical form
31. PDNF is also called _____________
Correct : A. sum of product canonical form
32. Max-terms of two statements are formed by introducing the connective _________.
Correct : A. disjunction
33. The Subset relation on a set of sets is ________.
Correct : A. partial ordering
34. A relation R is defined on the set of integers as xRy if and only if (x+y) is even. Which of
the following statement is TRUE?
Correct : C. R is an equivalence relation having two equivalence classes
35. If R = {(1, y), (1, z), (3, y)} then R power (-1)= ___________.
Correct : B. {(y, 1), (z, 1), (y, 3)}
36. Let R ={ (a,b),(c,d),(b,b)}, S = {(d,b),(c,b),(a,d)} then R composite S = ___________
Correct : D. {(c,b)}
37. Let R and S be two relations on a set of positive integers I. If R = {(a, 3a+a)},S = {(a,a+a)}
then R composition R composition R = __________.
Correct : C. {(a,27a+a)}
38. The number of relations from A = {a,b,c} to B = {1,2} are __________.
Correct : D. 64
39. The minimum number of edges in a connected graph with n vertices is ___________.
Correct : B. n-1
40. The number of distinct simple graphs with up to three nodes is _________.
Correct : A. 7
41. A graph is planar if and only if it does not contain ________.
Correct : D. sub graphs homeomorphic to k5 or k3,3
42. Maximum number of edges in an n-node undirected graph without self loops is ____.
Correct : A. [n(n-a)]/2
43. Number of distinct nodes in any elementary path of length p is ________.
Correct : C. p+1
44. The total number of edges in a complete graph of n vertices is _________.
Correct : D. [n(n-a)]/2
45. A directed complete graph of n vertices contains __________.
Correct : A. one arrow between each pair of distinct vertices
46. A directed graph G = (V, E) is said to be finite if its ________.
Correct : A. set V of vertices is finite
47. A state from which a deterministic finite state automata can never come out is called a
____________.
Correct : A. trape state
48. If a compound statement is made up of three simple statements then the number of rows in
the truth table is _______.
Correct : D. 8
49. Let R = {(3, 3), (6, 6), (9, 9), (12,12), (3,6), (6,3), (3, 9), (9, 3), (9, 12),(12,9)} be a relation
on the set A = {3, 6, 9, 12}. The relation is _________
Correct : D. equivalence relation
50. Let R={(1,b),(3,d),(2,b)} and S={(b,4),(2,5),(d,a)} be a relation then R composition
S=____.
Correct : B. {(1,4),(3,a),(2,4)}
51. If R= {(x, 2x)} and S= {(x, 4x)} then R composition S=____.
Correct : C. {(x, 8x)}
52. If R= {(x, 2x)} and S= {(x, 5x)} then R composition S=____.
Correct : D. {(x, 10x)}
53. A regular grammar contains rules of the form _____.
Correct : C. A tends to aB
54. A type-2 grammar contains the rules of the form is____.
Correct : C. A tends to aBC
55. Let R={(1, 3), (4, 2), (2, 2), (3, 3), (1, 1),(4,4)} be a relation on the set A={1, 2, 3, 4}. The
relation R is ____.
Correct : C. not symmetric
56. The NAND statement is a combination of ______.
Correct : A. NOT and AND
57. The NOR statement is a combination of ________.
Correct : B. NOT and OR
58. If a relation is reflexive then in the graph of a relation there must be a loop at _____.
Correct : A. each node
59. Which of the following traversal techniques lists the nodes of binary search in ascending
order?
Correct : C. in order
60. The grammar G ={{S},{0,1},P,S}} where P={S tends to 0S1 , S tends to S1} is a ________.
Correct : D. context free grammar
61. Which of the following regular expressions identifiers are true?
Correct : A. (r*)* = r
62. In a grammar or language LAMDA is used to denote _______.
Correct : A. empty word
63. The number of letters in a word is called ________.
Correct : A. length
64. If r is a regular expression then r* is a _______ expression.
Correct : A. regular
65. An example for regular grammar is _____.
Correct : C. S tends to aB
66. If all the productions have single non-terminal in the left hand side then the grammar
defined is ________grammar.
Correct : A. context free
67. In Backus Naur Form the symbol:: = is used instead of _______.
Correct : B. tends to
68. Any subset L of A* is called ________ over A.
Correct : A. Language
69. Let S be a start symbol and S -> aA, A -> BA, A -> a, B -> b be the productions in a
grammar then one of the string derived form the grammar is _____.
Correct : C. abba
70. If S is a start symbol and S -> AB, A -> aB, B -> b are the productions then a string
generated by the grammar is _______.
Correct : C. abb
71. In FSA ,the notation for M being in state S0, reading the input symbol a, moving one cell
right and reaching the state S1 is given by ________.
Correct : B. f(S0 , a) = S1
72. If "S -> aS, S -> a" are the productions in a grammar G, then the grammar is called_____.
Correct : A. regular grammar
73. The rank of the incidence matrix of any connected graph G with n vertices is ______.
Correct : C. n-1
74. The number of 1's in each row of an incidence matrix of a graph G is equal to _____.
Correct : A. the degree of the corresponding vertices
75. Each column of an incidence matrix of a graph G has exactly _______.
Correct : B. two 1's
76. An undirected graph is tripartite if and only if it has no circuits of _______ lengths
Correct : A. odd
77. A graph is bipartite if and only if its chromatic number is ________.
Correct : B. 2
78. G is strongly connected implies _________.
Correct : A. G is unilaterally connected.
79. The number of pendant vertices in a full binary tree with n vertices is ________.
Correct : C. (n+a)/2
80. The number of vertices in a full binary tree is _______.
Correct : A. odd
81. A binary tree with 2k vertices of level k has at least _______ vertices.
Correct : D. 2 power (k+1)-1
82. For a symmetric digraph, the adjacency matrix is _________.
Correct : A. symmetric
83. The diagonal entries of A A^T where A is the adjacency matrix are the _______.
Correct : A. outdegrees of the node
84. DFSA and NDFSA represent the ________ language.
Correct : A. regular
85. The chromatic number of the chess board is ______.
Correct : B. 2
86. The total number of degrees of an isolated node is _______.
Correct : A. 0
87. If G is a connected planar graph then it has a vertex of degree _______.
Correct : C. 5 or less
88. A product of the variable and their negation in a formula is called ________.
Correct : B. an elementary product
89. A formula consisting of disjunctions of min-terms is called _________.
Correct : C. PDNF
90. The less than relation < on real is __________.
Correct : D. not a partial ordering since it is not anti-symmetric and not reflexive
91. A relation R in X is said to be a ________, if it is reflexive and symmetric.
Correct : D. compatibility relation
92. The set X*X itself defines a relation in X is called a _____relation.
Correct : B. universal
93. A self complemented distributive lattice is called _______.
Correct : A. boolean algebra
94. Every finite subset of a lattice has ____________.
Correct : A. a Least Upper Bound and Greatest Lower Bound
95. A formula consisting of conjunctions of max-terms is called _________.
Correct : C. PCNF
96. The set of all divisors of 24 are ___________.
Correct : A. {1, 2, 3, 4, 6, 8, 12, 24}
97. Which of the following is Absorption Law?
Correct : B. a+(a*b)<=> a
98. In a bounded lattice, an element b belongs to L is called a complement of an element a
belongs to L if ______.
Correct : C. both a and b
99. If each non-empty subset of a lattice has a least upper bound and greatest lower bound then
the lattice is called ________.
Correct : A. complete
100. A __________ is a complemented distributive lattice.