GATE CS question library

Consider numbers represented in 4-bit Gray code. Let $h_{3}h_{2}h_{1}h_{0}$ be the Gray code representation of a number $n$ and let $g_{3}g_{2}g_{1}g_{0}$ be the Gray code of $(n+1)(modulo 16)$ value of the number. Which one of the following functions is correct?

We consider the addition of two $2's$ complement numbers $b_{n-1}b_{n-2}\dots b_{0}$ and $a_{n-1}a_{n-2}\dots a_{0}$. A binary adder for adding unsigned binary numbers is used to add the two numbers. The sum is denoted by $c_{n-1}c_{n-2}\dots c_{0}$ and the carry-out by $c_{out}$. Which one of the following options correctly identifies the overflow …

Consider a Boolean function $f(w,x,y,z)$. Suppose that exactly one of its inputs is allowed to change at a time. If the function happens to be true for two input vectors $i_{1}=\left \langle w_{1}, x_{1}, y_{1},z_{1}\right \rangle$ and $i_{2}=\left \langle w_{2}, x_{2}, y_{2},z_{2}\right \rangle$ , we would like the function to remain true as the input …

Consider the circuit in the diagram. The $\oplus$ operator represents Ex-OR. The D flip-flops are initialized to zeroes (cleared). The following data: $100110000$ is supplied to the “data” terminal in nine clock cycles. After that the values of $q_{2}q_{1}q_{0}$ are:

Given two three bit numbers $a_{2}a_{1}a_{0}$ and $b_{2}b_{1}b_{0}$ and $c$ the carry in, the function that represents the carry generate function when these two numbers are added is:

Consider the circuit above. Which one of the following options correctly represents $f\left(x,y,z\right)$

Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is:

Let $L_1$ be a regular language, $L_2$ be a deterministic context-free language and $L_3$ a recursively enumerable, but not recursive, language. Which one of the following statements is false?

Consider the following statements about the context free grammar $$G = \left \{ S \rightarrow SS, S \rightarrow ab, S \rightarrow ba, S \rightarrow \epsilon \right \}$$ $G$ is ambiguous $G$ produces all strings with equal number of $a$’s and $b$’s $G$ can be accepted by a deterministic PDA. Which combination below expresses all the true statements …

Let SHAM$_3$ be the problem of finding a Hamiltonian cycle in a graph $G=(V,E)$ with $|V|$ divisible by $3$ and DHAM$_3$ be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

For $s\in (0+1)^{*}$ let $d(s)$ denote the decimal value of $s ($e.g. $d (101) = 5 ).$ Let $$L=\left \{ s\in (0+1)^*\mid d(s) \text{ mod } 5=2 \text{ and }d(s) \text{ mod } 7\neq 4 \right \}$$Which one of the following statements is true?

If $s$ is a string over $(0+1)^*$ then let $n_0(s)$ denote the number of $0$’s in $s$ and $n_1(s)$ the number of $1$’s in $s$. Which one of the following languages is not regular?

A logical binary relation $\odot$, is defined as follows: …

Consider the following propositional statements: $P_1: ((A ∧ B) → C)) ≡ ((A → C) ∧ (B → C))$ $P_2: ((A ∨ B) → C)) ≡ ((A → C) ∨ (B → C))$ Which one of the following is true?

Which one of the first order predicate calculus statements given below correctly expresses the following English statement? Tigers and lions attack if they are hungry or threatened.

Let $S = \{1, 2, 3,\ldots, m\}, m >3.$ Let $X_1,\ldots,X_n$ be subsets of $S$ each of size $3.$ Define a function $f$ from $S$ to the set of natural numbers as, $f(i)$ is the number of sets $X_j$ that contain the element $i.$ That is $f(i)=\left | \left\{j \mid i\in X_j \right\} \right|$ then $\sum_{i=1}^{m} f(i)$ is:

Given a set of elements $N = {1, 2, ..., n}$ and two arbitrary subsets $A⊆N$ and $B⊆N$, how many of the n! permutations $\pi$ from $N$ to $N$ satisfy $\min(\pi(A)) = \min(\pi(B))$, where $\min(S)$ is the smallest integer in the set of integers $S$, and $\pi$(S) is the set of integers obtained by applying permutation $\pi$ to each …

$F$ is an $n\times n$ real matrix. $b$ is an $n\times 1$ real vector. Suppose there are two $n\times 1$ vectors, $u$ and $v$ such that, $u ≠ v$ and $Fu = b, Fv = b$. Which one of the following statements is false?

Let $E, F$ and $G$ be finite sets. Let $X = (E ∩ F) - (F ∩ G)$ and $Y = (E - (E ∩ G)) - (E - F)$. Which one of the following is true?

For each element in a set of size $2n$, an unbiased coin is tossed. The $2n$ coin tosses are independent. An element is chosen if the corresponding coin toss was a head. The probability that exactly $n$ elements are chosen is