GATE CS question library

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is __________.

A processor uses a $32$-bit instruction format and supports byte-addressable memory access. The $\text{ISA}$ of the processor has $150$ distinct instructions. The instructions are equally divided into two types, namely $\text{R}$-type and $\text{I}$-type, whose formats are shown below. R - type Instruction Format: \begin{array}{|l|l|l|l|l|} \hline …

Let $L_{1}$ be the language represented by the regular expression $b^{*} a b^{*}\left(a b^{*} a b^{*}\right)^{*}$ and $L_{2}=\left\{w \in(a+b)^{*}|| w \mid \leq 4\right\}$, where $|w|$ denotes the length of string $w$. The number of strings in $L_{2}$ which are also in $L_{1}$ is _________.

Let $Z_{n}$ be the group of integers $\{0,1,2, \ldots, n-1\}$ with addition modulo $n$ as the group operation. The number of elements in the group $Z_{2} \times Z_{3} \times Z_{4}$ that are their own inverses is ___________.

Consider a $32$-bit system with $4 \mathrm{~KB}$ page size and page table entries of size $4$ bytes each. Assume $1 \mathrm{~KB}=2^{10}$ bytes. The OS uses a $2$-level page table for memory management, with the page table containing an outer page directory and an inner page table. The $\text{OS}$ allocates a page for the outer page directory upon …

Consider the following augmented grammar, which is to be parsed with a $\text{SLR}$ parser. The set of terminals is $\{a, b, c, d, \#, @\}$ $$\begin{array}{l} S^{\prime} \rightarrow S \\ S \rightarrow S S|A a| b A c|B c| b B a \\ A \rightarrow d \# \\ B \rightarrow @ \end{array}$$ Let …