GATE CS 2025 Set 1 - W3Colleges

Question 41

MCQ · 2 marks · −0.66

Let $A$ be a $2 \times 2$ matrix as given.

\[ A = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \]

What are the eigenvalues of the matrix $A^{13}$?

$1, -1$ $2\sqrt{2}, -2\sqrt{2}$ $4\sqrt{2}, -4\sqrt{2}$ $64\sqrt{2}, -64\sqrt{2}$

Explanation

Answer: (D)

Squaring $A$ gives a shortcut:

\[ A^2 = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} = 2I, \qquad A^{13} = (A^2)^6 A = 2^6 A = 64A. \]

The eigenvalues of $A$ satisfy $\det(A - \lambda I) = (1 - \lambda)(-1 - \lambda) - 1 = \lambda^2 - 2 = 0$, so $\lambda = \pm\sqrt{2}$. Hence $A^{13} = 64A$ has eigenvalues $\pm 64\sqrt{2}$, the same as $(\pm\sqrt{2})^{13} = \pm 2^6\sqrt{2}$.

Answer: D

Question 42

MCQ · 2 marks · −0.66

Consider the following four variable Boolean function in sum-of-product form

\[ F(b_3, b_2, b_1, b_0) = \sum (0, 2, 4, 8, 10, 11, 12). \]

where the value of the function is computed by considering $b_3 b_2 b_1 b_0$ as a 4-bit binary number, where $b_3$ denotes the most significant bit and $b_0$ denotes the least significant bit. Note that there are no don’t care terms. Which ONE of the following options is the CORRECT minimized Boolean expression for $F$?

$\bar{b}_1 \bar{b}_0 + \bar{b}_2 \bar{b}_0 + b_1 \bar{b}_2 b_3$ $\bar{b}_1 \bar{b}_0 + \bar{b}_2 \bar{b}_0$ $\bar{b}_2 \bar{b}_0 + b_1 b_2 b_3$ $\bar{b}_0 \bar{b}_2 + \bar{b}_3$

Explanation

Answer: (A)

Write the minterms as $b_3 b_2 b_1 b_0$: 0 = 0000, 2 = 0010, 4 = 0100, 8 = 1000, 10 = 1010, 11 = 1011, 12 = 1100. Group them on a K-map:

$\{0, 4, 8, 12\}$ all have $b_1 = b_0 = 0$, giving $\bar{b}_1 \bar{b}_0$.
$\{0, 2, 8, 10\}$ all have $b_2 = b_0 = 0$, giving $\bar{b}_2 \bar{b}_0$.
11 (1011) has only one neighbouring 1, namely 10 (1010), so it needs the pair $\{10, 11\}$, giving $b_3 \bar{b}_2 b_1$.

All three groups are essential and together cover exactly the seven minterms, so $F = \bar{b}_1 \bar{b}_0 + \bar{b}_2 \bar{b}_0 + b_1 \bar{b}_2 b_3$. Option B misses minterm 11, C covers 14 and 15 (not in $F$), and D covers 1, 3, 5, 6 and 7.

Answer: A

Question 43

MCQ · 2 marks · −0.66

Let $G(V, E)$ be an undirected and unweighted graph with 100 vertices. Let $d(u, v)$ denote the number of edges in a shortest path between vertices $u$ and $v$ in $V$. Let the maximum value of $d(u, v),\ u, v \in V$ such that $u \ne v$, be 30. Let $T$ be any breadth-first-search tree of $G$. Which ONE of the given options is CORRECT for every such graph $G$?

The height of $T$ is exactly 15. The height of $T$ is exactly 30. The height of $T$ is at least 15. The height of $T$ is at least 30.

Explanation

Answer: (C)

In a BFS tree rooted at $r$, every vertex sits at depth equal to its shortest-path distance from $r$, so the height of $T$ is the largest distance from $r$ to any vertex.

Take $u, v$ with $d(u, v) = 30$. For any root $r$, $30 = d(u, v) \le d(u, r) + d(r, v)$, so $r$ is at distance at least 15 from $u$ or from $v$. Hence the height is always at least 15 (and never more than 30).

Both extremes occur: take a path of 31 vertices and attach the other 69 vertices to its middle vertex. BFS from the middle vertex gives height 15, and BFS from an end of the path gives height 30. So A, B and D can fail, and only C holds for every such graph.

Answer: C

Question 44

MCQ · 2 marks · −0.66

Consider the following two languages over the alphabet $\{a, b\}$:

\[ L_1 = \{\, \alpha\beta\alpha \mid \alpha \in \{a, b\}^+ \text{ AND } \beta \in \{a, b\}^+ \,\} \]

\[ L_2 = \{\, \alpha\beta\alpha \mid \alpha \in \{a\}^+ \text{ AND } \beta \in \{a, b\}^+ \,\} \]

Which ONE of the following statements is CORRECT?

Both $L_1$ and $L_2$ are regular languages. $L_1$ is a regular language but $L_2$ is not a regular language. $L_1$ is not a regular language but $L_2$ is a regular language. Neither $L_1$ nor $L_2$ is a regular language.

Explanation

Answer: (C)

$L_2$: $\alpha$ is a block of a's, so any $a^k \beta a^k$ can be rewritten with $\alpha = a$ by moving the extra a's into the middle part. So $L_2 = {a(a+b)^+a}$, the strings of length at least 3 that start and end with $a$, which is regular.
$L_1$: shrinking $\alpha$ to one symbol fails, because $\alpha$ may start and end with different symbols; for example $abaab = (ab)(a)(ab) \in L_1$. A finite automaton would have to remember an arbitrarily long $\alpha$.
Pumping lemma proof for $L_1$: $w = a^n b\, a\, a^n b \in L_1$ ($\alpha = a^n b$, $\beta = a$). Pumping up the leading a's gives $a^{n+k} b\, a^{n+1} b$. Here $\alpha$ must be a prefix ending in $b$, i.e. $a^{n+k} b$, and that is a suffix only when $k = 1$, when nothing is left for $\beta$. So the pumped string is not in $L_1$, and $L_1$ is not regular.

Answer: C

Question 45

MCQ · 2 marks · −0.66

Consider the following two languages over the alphabet $\{a, b, c\}$, where $m$ and $n$ are natural numbers.

\[ L_1 = \{a^m b^m c^{m+n} \mid m, n \ge 1\} \]

\[ L_2 = \{a^m b^n c^{m+n} \mid m, n \ge 1\} \]

Which ONE of the following statements is CORRECT?

Both $L_1$ and $L_2$ are context-free languages. $L_1$ is a context-free language but $L_2$ is not a context-free language. $L_1$ is not a context-free language but $L_2$ is a context-free language. Neither $L_1$ nor $L_2$ are context-free languages.

Explanation

Answer: (C)

$L_2$ is context-free: $a^m b^n c^{m+n} = a^m\,(b^n c^n)\,c^m$ is a nested pattern, generated by $S \to aSc \mid aAc$, $A \to bAc \mid bc$. A PDA pushes one symbol for every $a$ and $b$ and pops one for every $c$.
$L_1$ is not context-free: it needs $\#a = \#b$ and also $\#c \gt \#a$ (because $n \ge 1$), so the same count $m$ must be compared twice, but the single stack is used up matching the a's against the b's.
Pumping lemma check: take $a^p b^p c^{p+1}$. The pumped part (length $\le p$) cannot touch both a's and c's. If it contains a's or b's, pumping up gives $\#a \ne \#b$ or $\#a = \#b \ge p + 1 = \#c$; if it contains only c's, pumping down gives $\#c \le p = \#a$. Either way the string leaves $L_1$.

Answer: C

Question 46

MSQ · 2 marks

Which of the following statement(s) is/are TRUE while computing First and Follow during top down parsing by a compiler?

For a production $A \to \epsilon$, $\epsilon$ will be added to $First(A)$. If there is any input right end marker, it will be added to $First(S)$, where $S$ is the start symbol. For a production $A \to \epsilon$, $\epsilon$ will be added to $Follow(A)$. If there is any input right end marker, it will be added to $Follow(S)$, where $S$ is the start symbol.

Explanation

Answer: (A), (D)

(A) True: $\epsilon \in First(A)$ whenever $A$ can derive the empty string, and $A \to \epsilon$ does so directly.
(B) False: $First$ sets contain the terminals (and possibly $\epsilon$) that can begin a string derived from a symbol; the end marker $\$$ never goes into a $First$ set.
(C) False: $Follow(A)$ contains the terminals (and $\$$) that can appear just after $A$ in a sentential form; $\epsilon$ is never added to a $Follow$ set.
(D) True: the first rule for $Follow$ sets puts the right end marker $\$$ into $Follow(S)$, because the input ends right after a string derived from $S$.

Answer: A, D

Question 47

MSQ · 2 marks

Consider a relational schema $team(name, city, owner)$, with functional dependencies $\{name \to city,\ name \to owner\}$.

The relation $team$ is decomposed into two relations, $t1(name, city)$ and $t2(name, owner)$. Which of the following statement(s) is/are TRUE?

The relation $team$ is NOT in BCNF. The relations $t1$ and $t2$ are in BCNF. The decomposition constitutes a lossless join. The relation $team$ is NOT in 3NF.

Explanation

Answer: (B), (C)

Key: $name^+ = \{name, city, owner\}$, so $name$ is a candidate key of $team$. Both FDs have this key on the left, so $team$ is already in BCNF, and therefore in 3NF too. So (A) and (D) are false.
(B) True: in $t1$ the only FD is $name \to city$ and in $t2$ it is $name \to owner$; in each, $name$ is a key. (Any relation with just two attributes is in BCNF anyway.)
(C) True: the common attribute of $t1$ and $t2$ is $name$, which is a key of $t1$ (and of $t2$), so joining them on $name$ gives back exactly the original relation.

Answer: B, C

Question 48

MSQ · 2 marks

Which of the following predicate logic formulae/formula is/are CORRECT representation(s) of the statement: “Everyone has exactly one mother”?

The meanings of the predicates used are:

$mother(y, x)$: $y$ is the mother of $x$
$noteq(x, y)$: $x$ and $y$ are not equal

$\forall x \exists y \exists z \big(mother(y, x) \land \lnot mother(z, x)\big)$ $\forall x \exists y \big[mother(y, x) \land \forall z \big(noteq(z, y) \to \lnot mother(z, x)\big)\big]$ $\forall x \forall y [mother(y, x) \to \exists z (mother(z, x) \land \lnot noteq(z, y))]$ $\forall x \exists y \big[mother(y, x) \land \lnot \exists z \big(noteq(z, y) \land mother(z, x)\big)\big]$

Explanation

Answer: (B), (D)

“Exactly one mother” means: $x$ has at least one mother $y$, and nobody other than $y$ is a mother of $x$.

(A) False: it only says $x$ has some mother $y$ and some non-mother $z$; a second mother is not ruled out.
(B) True: $y$ is a mother of $x$, and every $z$ different from $y$ is not a mother of $x$.
(C) False: it says that if $y$ is a mother of $x$, then some $z$ equal to $y$ is a mother of $x$. That is always true (take $z = y$), so it neither forces a mother to exist nor limits how many there are.
(D) True: $\lnot \exists z\, (noteq(z, y) \land mother(z, x))$ is equivalent to $\forall z\, (noteq(z, y) \to \lnot mother(z, x))$, so (D) says the same as (B).

Answer: B, D

Question 49

MSQ · 2 marks

$A = \{0, 1, 2, 3, \ldots\}$ is the set of non-negative integers. Let $\mathrm{F}$ be the set of functions from $A$ to itself. For any two functions, $f_1, f_2 \in \mathrm{F}$, we define

\[(f_1 \odot f_2)(n) = f_1(n) + f_2(n)\]

for every number $n$ in $A$. Which of the following is/are CORRECT about the mathematical structure $(\mathrm{F}, \odot)$?

$(\mathrm{F}, \odot)$ is an Abelian group. $(\mathrm{F}, \odot)$ is an Abelian monoid. $(\mathrm{F}, \odot)$ is a non-Abelian group. $(\mathrm{F}, \odot)$ is a non-Abelian monoid.

Explanation

Answer: (B)

Check the axioms for pointwise addition of functions from $A$ to $A$.

Closure: $f_1(n) + f_2(n)$ is again a non-negative integer, so $f_1 \odot f_2 \in \mathrm{F}$.
Associativity and commutativity come straight from ordinary addition at each $n$.
Identity: the zero function $z(n) = 0$ is in $\mathrm{F}$, and $f \odot z = f$.
Inverses fail: for the constant function $f(n) = 1$, the inverse would need $g(n) = -1$, which is not in $A$.

So $(\mathrm{F}, \odot)$ is a commutative (Abelian) monoid but not a group. (A) and (C) are wrong because it is not a group; (D) is wrong because $\odot$ is commutative.

Answer: B

Question 50

MSQ · 2 marks

Consider the following deterministic finite automaton (DFA) defined over the alphabet, $\Sigma = \{a, b\}$. Identify which of the following language(s) is/are accepted by the given DFA.

DFA with four states in a row over a and b; the leftmost is the start state and the rightmost is the only accepting state

The set of all strings containing an even number of $b$’s. The set of all strings containing the pattern $bab$. The set of all strings ending with the pattern $bab$. The set of all strings not containing the pattern $aba$.

Explanation

Answer: (C)

Label the states $q_0$ (start), $q_1$, $q_2$, $q_3$ (accepting) from left to right. $q_0$ loops on $a$ and goes to $q_1$ on $b$; $q_1$ loops on $b$ and goes to $q_2$ on $a$; $q_2$ goes to $q_3$ on $b$ and back to $q_0$ on $a$; $q_3$ goes to $q_2$ on $a$ and to $q_1$ on $b$.

So $q_1$, $q_2$ and $q_3$ mean that the input read so far ends with $b$, $ba$ and $bab$. The DFA accepts exactly the strings ending with $bab$, so (C) is correct.

(A) is wrong: $bb$ has an even number of $b$'s but is rejected, while $babab$ has three and is accepted.
(B) is wrong: $baba$ contains $bab$ but ends in $q_2$.
(D) is wrong: $b$ does not contain $aba$ but is rejected.

Answer: C

Computer Science and Information Technology