Jawaharlal Nehru Technological University Hyderabad 2001 B.Tech Computer Science and Engineering gate - Question Paper

R3 (a,b) iff a.b > 0 over the set of non-zero rational numbers
R4 (a,b) iff |a œ b|
=
2 over the set of natural numbers
Which of the subsequent statements is correct?
(a) R1 and R2 are equivalence relations, R3 and R4 are not
(b) R1 and R3 are equivalence relations, R2 and R4 are not
(c) R1 and R4 are equivalence relations, R2 and R3 are not
(d) R1, R2, R3 and R4 are all equivalence relations
1.3 Consider 2 well-formed formulas in prepositional logic
F1: P
¬
P F2: (P
¬
P)
(
¬
P P)
Which of the subsequent statements is correct?
(a) F1 is satisfiable, F2 is valid (b) F1 unsatisfiable, F2 is satisfiable
(c) F1 is unsatisfiable, F2 is valid (d) F1 and F2 are both satisfiable
1.4 consider the subsequent 2 statements:
{ }
0 1
n
=
is a regular language
2
n
S1:
{ }
S2:
0 one 0 one and 1
m n
= =
is a regular language
m n m n
+
Which of the subsequent statements is correct?
(a) Only S1 is accurate (b) Only S2 is accurate
(c) Both S1 and S2 are accurate (d) None of S1 and S2 is accurate
Jo
1.5 Which of the subsequent statements s true?
(a) If a language is situation free it can always be accepted by a deterministic
push-down automaton
(b) The union of 2 situation free languages is situation free
(c) The intersection of 2 situation free languages is situation free
(d) The complement of a situation free language is situation free
1.6 provided an arbitary non-deterministic finite automaton (NFA) with N states, the
maximum number of states in an equivalent minimized DFA is at lowest
(a) N
(b) 2
(c) 2N (d) N!
2
N
1.7 More than 1 word are put in 1 cache block to
(a) exploit the temporal locality of reference in a program
(b) exploit the spatial locality of reference in a program
(c) decrease the miss penalty
(d) none of the above
1.8 Which of the subsequent statements is false?
(a) Virtual memory implements the translation of a program‘s address space into
physical memory address space
(b) Virtual memory allows every program to exceed the size of the primary

Earning:   Approval pending.