GATE CS question library

A Boolean function $f$ is to be realized only by $\text{NOR}$ gates. Its $K$-map is given below: The realization is

The below figure shows four $\text{D}$-type flip-flops connected as a shift register using a $\text{XOR}$ gate. The initial state and three subsequent states for three clock pulses are also given. …

The Boolean expression $A \oplus B \oplus A$ is equivalent to

State whether the following statements are TRUE or FALSE: A relation $r$ with schema $(X, Y)$ satisfies the function dependency $X \rightarrow Y$, The tuples $\langle 1, 2\rangle$ and $\langle 2, 2 \rangle$ can both be in $r$ simultaneously.

State whether the following statements are TRUE or FALSE: The problem as to whether a Turing machine $M$ accepts input $w$ is undecidable.

State whether the following statement are TRUE or FALSE. $A$ is recursive if both $A$ and its complement are accepted by Turing machines.

State whether the following statements are TRUE or FALSE: The intersection of two CFL's is also a CFL.

State whether the following statements are TRUE or FALSE: A minimal DFA that is equivalent to an NDFA with $n$ nodes has always $2^{n}$ states.

State whether the following statements are TRUE or FALSE: Regularity is preserved under the operation of string reversal.

State whether the following statements are TRUE or FALSE: All subsets of regular sets are regular.

State whether the following statements are TRUE or FALSE: If the number of leaves in a tree is not a power of $2,$ then the tree is not a binary tree.

State whether the following statements are TRUE or FALSE: The union of two equivalence relations is also an equivalence relation.

State whether the following statements are TRUE or FALSE: It is possible to construct a binary tree uniquely whose pre-order and post-order traversals are given?

State whether the following statements are TRUE or FALSE: Data transfer between a microprocessor and an I/O device is usually faster in memory-mapped-I/O scheme than in I/O-mapped -I/O scheme.

State whether the following statements are TRUE or FALSE In a microprocessor-based system, if a bus (DMA) request and an interrupt request arrive sumultaneously, the microprocessor attends first to the bus request.

If $f(x_{i}).f(x_{i+1})< 0$ then

The simplex method is so named because

A square matrix is singular whenever

The equation $7x^{7}+14x^{6}+12x^{5}+3x^{4}+12x^{3}+10x^{2}+5x+7=0$ has

If $a, b,$ and $c$ are constants, which of the following is a linear inequality?