CS and IT GATE 2021 Set-1 Questions with Answer

Ques 40 Theory of Computation

Consider the following recurrence relation.
T(n) = T(n/2) + T(2n/5) + 7n if n > 0
T(n) = 1 if n = 0
Which one of the following options is correct?

T(n) = Θ(n5/2)

T(n) = Θ(n log n)

T(n) = Θ(n)

T(n) = Θ((log n)5/2)

Ques 41 Theory of Computation

Consider the following context-free grammar where the set of terminals is {a, b, c, d, f}.
S -> daT | Rf
T -> aS | baT | ε
R -> caTR | ε
The following is a partially-filled LL(1) parsing table.

Which one of the following choices represents the correct combination for the numbered cells in the parsing table (“blank” denotes that the corresponding cell is empty)?

S -> Rf, T -> ε, T -> ε, S -> Rf

S -> Rf, T -> ε, T -> ε, blank

S -> Rf, blank, T -> ε, blank

blank, S -> Rf, blank, blank

Ques 42 Theory of Computation

Consider the following language.
L = {w ∈ {0, 1}* | w ends with the substring 011}
Which one of the following deterministic finite automata accepts L?

Ques 43 Theory of Computation

For a Turing machine M, denotes an encoding of M. Consider the following two languages.
L1 = { | M takes more than 2021 steps on all inputs}
L2 = { | M takes more than 2021 steps on some input}
Which one of the following options is correct?

Both L1 and L2 are decidable.

L1 is decidable and L2 is undecidable.

L1 is undecidable and L2 is decidable.

Both L1 and L2 are undecidable.

Ques 44 Theory of Computation

An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components. Let T be a DFS tree obtained by doing DFS in a connected undirected graph G. Which of the following options is/are correct?

Root of T can never be an articulation point in G.

Root of T is an articulation point in G if and only if it has 2 or more children.

A leaf of T can be an articulation point in G.

If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u.

Ques 45 Theory of Computation

A relation R is said to be circular if aRb and bRc together imply cRa. Which of the following options is/are correct?

If a relation S is reflexive and symmetric, then S is an equivalence relation.

If a relation S is circular and symmetric, then S is an equivalence relation.

If a relation S is reflexive and circular, then S is an equivalence relation.

If a relation S is transitive and circular, then S is an equivalence relation.

Ques 46 Theory of Computation

Define Rn to be the maximum amount earned by cutting a rod of length n meters into one or more pieces of integer length and selling them. For i > 0, let p[i] denote the selling price of a rod whose length is i meters. Consider the array of prices:
p = 1, p = 5, p = 8, p = 9, p = 10, p = 17, p = 18
Which of the following statements is/are correct about R7?

R7 = 18

R7 = 19

R7 is achieved by three different solutions.

R7 cannot be achieved by a solution consisting of three pieces.

Ques 47 Theory of Computation

Consider the following statements.
S1: Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1).
S2: For any context-free grammar, there is a parser that takes at most O(n³) time to parse a string of length n.
Which one of the following options is correct?

S1 is true and S2 is false.

S1 is false and S2 is true.

Both S1 and S2 are true.

Both S1 and S2 are false.

Ques 48 Theory of Computation

A relation R is said to be circular if aRb and bRc together imply cRa.
Which of the following options is/are correct?

If a relation S is reflexive and symmetric, then S is an equivalence relation.

If a relation S is circular and symmetric, then S is an equivalence relation.

If a relation S is reflexive and circular, then S is an equivalence relation.

If a relation S is transitive and circular, then S is an equivalence relation.

Ques 49 Theory of Computation

Consider the following statements.
S1: For every infinite regular language L, there exists a subset L′ of L such that L′ is infinite and context-free.
S2: For every context-free language L, there exists a subset L′ of L such that L′ is infinite and regular.
Which one of the following options is correct?

S1 is true and S2 is false.

S1 is false and S2 is true.

Both S1 and S2 are true.

Both S1 and S2 are false.

Ques 50 Theory of Computation

Consider the following statements.
S1: If L1 is a context-free language and L2 is a regular language, then L1 − L2 is a context-free language.
S2: If L1 is a context-free language and L2 is a regular language, then L1 ∩ L2 is a regular language.
Which one of the following options is correct?

S1 is true and S2 is false.

S1 is false and S2 is true.

Both S1 and S2 are true.

Both S1 and S2 are false.

Ques 51 Theory of Computation

An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components.
Let T be a DFS tree obtained by doing DFS in a connected undirected graph G.
Which of the following options is/are correct?

Root of T can never be an articulation point in G.

Root of T is an articulation point in G if and only if it has 2 or more children.

A leaf of T can be an articulation point in G.

If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u.

Ques 52 Theory of Computation

Consider the following statements.
S₁: Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1).
S₂: For any context-free grammar, there is a parser that takes at most O(n³) time to parse a string of length n.
Which one of the following options is correct?

S₁ is true and S₂ is false

S₁ is false and S₂ is true

S₁ is true and S₂ is true

S₁ is false and S₂ is false

1 2 3 4 5

Total Unique Visitors

Loading......

CS/IT Gate Yearwise

CS and IT GATE 2021 Set-1 Questions with Answer