Uttar Pradesh Technical University (UPTU) 2006 B.Tech Computer Science Information Technology GATE - Question Paper

d (s) mod five = two and d (s) mod seven = 4)
Which 1 of the subsequent 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
31. Let SHAM3 be the issue of finding a Hamiltonian cycle in a graph G =(V,E)with V
divisible by three and DHAM3 be the issue of determining if a Hamiltonian cycle exists in such

graphs. Which 1 of the subsequent is true?
A B AoB
actual actual actual
True
Fals
e
True
Fals
e
actual False
Fals
e
Fals
e
True
(A) Both DHAM3 and SHAM3 are NP-hard
(B) SHAM3 is NP-hard, but DHAM3 is not
(C) DHAM3 is NP-hard, but SHAM3 is not
(D) Neither DHAM3 nor SHAM3 is NP-hard
32. Consider the subsequent statements about the situation 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 beneath expresses all the actual statements about G?
(A) I only
(B) I and III only
(C) II and III only
(D) I, II and III
33. Let L1 be a regular language, L2 be a deterministic context-free language and L3 a
recursively enumerable, but not recursive, language. Which 1 of the subsequent statements is
false?
(A) L1 fl L is a deterministic CFL
(B) L3 fl L is recursive
(C) L1 U L2 is situation free
(D) L1 fl L fl L3 is recursively enumerable
34. Consider the regular language L =(111+11111)*. The minimum number of
states in any DFA accepting this languages is:
(A) 3
(B) 5
(C) 8
(D) 9

35.
Consider the circuit above. Which 1 of the subsequent choices correctly represents f(x,y,z)?
(A) xz+xy+yz
(B) xz+xy+yz
(C) xz+xy+yz
(D) xz+xy+yz
36. provided 2 3 bit numbers a2a1a0 and b2b1b0 and c, the carry in, the function that
represents the carry generate function when these 2 numbers are added is:
(A) a2b2 + a2a1b1 + a2a1a0b0 + a2a0b1b0 + a1b2b1 + a1a0b2b0 + a0b2b1b0
(B) a2b2 + a2b1b0 + a2a1b1b0 + a1a0b2b1 + a1a0b2 + a1a0b2b0 + a2a0b1b0

Earning:   Approval pending.