CS GATE 2015 - Online Test
Q1. Consider the following two statements.
S1 : if a candidate is known to be corrupt, then he will not be elected
S2 : if a candidate is kind, he will be elected
Which one of the following statements follows from S1 and S2 per sound interference rules of
logic?
Answer : Option C
Explaination / Solution:
Let P: candidate known to be corrupt
q: candidate will be elected
r: candidate is kind
S1 = p ⟶ ~ q
= q ⟶~p
S2 = r ⟶ q
i.e., If a person is kind, he is not known to be corrupt
Option is C
Q2. Match the following:
Answer : Option C
Explaination / Solution:
Lemical Analyzer uses DFA to recognize the longest possible input sequence that makes up a
token. Parser takes input in the form of tokens and usually builds a data structure in the form
of parse tree. Here parse tree can be termed as a Production tree as parser uses production of
the grammar to check whether generated tokens form a meaningful compression).
Register allocation can be reduced to K-colouring problem where K is the number of registers
available on the target architecture.
Post order traversal of expression tree gives postfix notation for a given expression & this
post fix notation can be evaluated using stack.
Q3. Which one of the following well formed formulae is tautology?
Answer : Option C
Explaination / Solution:
Q4. Consider the following statements
I. The complement of every Turing decidable language is Turing decidable
II. There exists some language which is in NP but is not turing decidable
III. If L is a language in NP, L is turing decidable
Which of the above statements is/are true?
Answer : Option D
Explaination / Solution:
Turing decidable ⟶ Recursive language
Turing recognizable ⟶ Recursive enumerable language
I) Complement of turning decidable language is decidable which is true.
III) True ( Theorem )
Which violates (II) hence key is D
Q5. Consider the alphabet ∑ = {0.1},
the null/empty string λ and the sets of strings
X0 , X1 , and
X2 generated by the corresponding non-terminals of regular grammar. X0, X1, and X2 are
related as follows:
X0 = 1X1
X1 = 0X1 + 1X2
X2 = 0X1 + {λ}
Which one of the following choices precisely represents the strings in X0?
Answer : Option C
Explaination / Solution:
No Explaination.
Q6. Which of the following languages is/are regular?
Answer : Option A
Explaination / Solution:
Hence
m ≠ n, that mean n is greater than m, or m is greater than n.
So we need memory, so we can‟t draw DfA for it.
Q7. We __________________ our friend‟s birthday and we ______________ how to make it up
to him.
Answer : Option C
Explaination / Solution:
No Explaination.
Q8. Let R be the relation on the set of positive integers such that a aRb if and only if a and b are
distinct and have a common divisor other than 1. Which one of the following statements
about R is true?
Answer : Option D
Explaination / Solution:
R is not reflexive as each element can‟t be related to itself.
R is symmetric
Let a = 3, b = 6 and c = 10 then 3 and 6 have a common division other than 1
6 and 10 have a common division other than 1
but 3 &10 have no common division other than 1
3R6 and 6R10 but
3R10
R is not transitive
Q9. In the context of abstract-syntax-tree (AST) and control-flow-graph (CFG), which one of the
following is TRUE?
Answer : Option C
Explaination / Solution:
Optional (A) is not true when CFG contains cycle
Option (B) is false as CFG can contain cycle
Option (D) is false as a single node can contain block of statements.
Q10. Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3-SAT
and 3 -SAT reduces in polynomial time to Q2. Then which one of following is consistent with
the above statement?
Answer : Option A
Explaination / Solution:
