CS GATE 2013 - Online Test
Q1. The following code segment is executed on a processor which allows only register operands in
its instructions. Each instruction can have almost two source operands and one destination operand.
Assume that all variables are dead after this code segment
c = a + b;
d = c * a;
e = c + a;
x = c *c;
if (x > a) {
y = a * a;
}
else {
d = d * d;
e = e * e;
}
Suppose the instruction set architecture of the processor has only two registers. The only allowed
compiler optimization is code motion, which moves statements from one place to another while
preserving correctness. What is the minimum number of spills to memory in the compiled code?
Answer : Option B
Explaination / Solution:
After applying the code motion optimization the statement d=c*a; and e=c+a; can be moved
down to else block as d and e are not used anywhere before that and also value of a and c is
not changing.
In the above code total number of spills to memory is 1
Q2. Relation R has eight attributes ABCDEFGH. Fields of R contain only atomic values.
F = {CH → G, A → BC, B → CFH, E → A, F → EG} is a set of functional dependencies (FDs) so that F+ is exactly the set of FDs that hold for R
The relation R is
Answer : Option A
Explaination / Solution:
A → BC,B → CFH and F → EG are partial dependencies. Hence it is in 1NF but not in 2NF
Q3. Consider the languages L1 = Φ and L2 = {a} . Which one of the following represents L1 L2* UL1* ?
Answer : Option A
Explaination / Solution:
No Explaination.
Q4. The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have almost two source operands and one destination operand.
Assume that all variables are dead after this code segment
c = a + b;
d = c * a;
e = c + a;
x = c *c;
if (x > a) {
y = a * a;
}
else {
d = d * d;
e = e * e;
}
What is the minimum number of registers needed in the instruction set architecture of the
processor to compile this code segment without any spill to memory? Do not apply any
optimization other than optimizing register allocation
Answer : Option B
Explaination / Solution:
In the above code minimum number of registers needed are = 4
Q5. Which of the following is/are undecidable?
1. G is a CFG. Is L (G) = Φ?
2. G is a CFG. IS L (G) = Σ*?
3. M is a Turning machine. Is L(M) regular?
4. A is a DFA and N is a NFA. Is L (A) = L (N) ?
Answer : Option D
Explaination / Solution:
There is an algorithm to check whether the given CFG is empty, finite or infinite and also to
convert NFA to DFA hence 1 and 4 are decidable
Q6. Consider the following two sets of LR(1) items of an LR(1) grammar
X → c.X, c / d X → c.X, $
X → .cX, c / d X → .cX, $
X → .d, c / d X → .d, $
Which of the following statements related to merging of the two sets in the corresponding
LALR parser is/are FALSE?
1. Cannot be merged since look aheads are different
2. Can be merged but will result in S–R conflict
3. Can be merged but will result in R–R conflict
4. Cannot be merged since goto on c will lead to two different sets
Answer : Option D
Explaination / Solution:
1. Merging of two states depends on core part (production rule with dot operator), not on
look aheads.
2. The two states are not containing Reduce item ,So after merging, the merged state can not
contain any S-R conflict
3. As there is no Reduce item in any of the state, so can’t have R-R conflict.
4. Merging of stats does not depend on further goto on any terminal.
So all statements are false.
Q7. Consider the DFA given below.
Which of the following are FALSE?
1. Complement of L(A) is context–free
2. L(A) = L ((11*0+0)(0+1)*0*1*)
3. For the language accepted by A, A is the minimal DFA
4. A accepts all strings over {0, 1} of length at least 2
Answer : Option D
Explaination / Solution:
(1) L(A) is regular, its complement is also regular and if it is regular it is also context free.
(2) L(A) = (11*0+0)(0+1)*0*1* = 1*0(0+1)* Language has all strings where each string contains ‘0’.
(3) A is not minimal, it can be constructed with 2 states
(4) Language has all strings, where each string contains ‘0’. (atleast length one)
Q8. Consider the following languages
Which one of the following statements is FALSE?
Answer : Option D
Explaination / Solution:
Q9. Complete the sentence:
Universalism is to particularism as diffuseness is to ________
Answer : Option A
Explaination / Solution:
The relation is that of antonyms
Q10. Consider an undirected random graph of eight vertices. The probability that there is an edge
between a pair of vertices is ½. What is the expected number of unordered cycles of length
three?
Answer : Option C
Explaination / Solution:
P(edge) = 1/2
Number of ways we can choose the vertices out of 8 is 
(Three edges in each cycle)
Expected number of unordered cycles of length 3 = 
