GATE CSE 2019

A certain processor uses a fully associative cache of size 16 kB, The cache block size is 16 bytes. Assume that the main memory is byte addressable and uses a 32-bit address. How many bits are required for the Tag and the Index fields respectively in the addresses generated by the processor?

The chip select logic for a certain DRAM chip in a memory system design is shown below. Assume that the memory system has 16 address lines denoted by A_{15} \; to \; A_0. What is the range of address (in hexadecimal) of the memory system that can get enabled by the chip select (CS) signal?

Which one of the following kinds of derivation is used by LR parsers?

In 16-bit 2's complement representation, the decimal number -28 is:

Let U=\{1,2,,...n\}. Let A=\{(x,X)|x\in X,X\subseteq U\}. Consider the following two statements on |A|.

I. |A|=n2^{n-1}
II. |A|=\sum_{k=1}^{n}k\binom{n}{k}

Which of the above statements is/are TRUE?

Which one of the following is NOT a valid identity?

If L is a regular language over \Sigma =\{a,b\}, which one of the following languages is NOT regular ?

Consider Z = X - Y where X, Y and Z are all in sign-magnitude form. X and Y are each represented in n bits. To avoid overflow, the representation of Z would require a minimum of:

Let X be a square matrix. Consider the following two statements on X.

I. X is invertible
II. Determinant of X is non-zero

Which one of the following is TRUE?

Let G be an arbitrary group. Consider the following relations on G:

R1: \forall a,b \in G, aR_1b if and only if \exists g \in G such that a=g^{-1}bg
R2: \forall a,b \in G, aR_2b if and only if a=b^{-1}

Which of the above is/are equivalence relation/relations?