GATE CS question library

Which of the following describes a handle (as applicable to LR-parsing) appropriately?

Which of the following is true for the language $$\left\{ a^p \mid p \text{ is a prime } \right \}?$$

Given $f_1$, $f_3$ and $f$ in canonical sum of products form (in decimal) for the circuit $f_1 = \Sigma m(4, 5, 6, 7, 8)$ $f_3 = \Sigma m(1, 6, 15)$ $f = \Sigma m(1, 6, 8, 15)$ then $f_2$ is

The most efficient algorithm for finding the number of connected components in an undirected graph on $n$ vertices and $m$ edges has time complexity

Let $r$ denote number system radix. The only value(s) of $r$ that satisfy the equation $\sqrt{121_r}={11}_r$ is/are

In the Karnaugh map shown below, $X$ denotes a don’t care term. What is the minimal form of the function represented by the Karnaugh map?

In the IEEE floating point representation the hexadecimal value $0\text{x}00000000$ corresponds to

The following system of equations $x_1 + x_2 + 2x_3 = 1$ $x_1 + 2x_2 + 3x_3 = 2$ $x_1 + 4x_2 + αx_3 = 4$ has a unique solution. The only possible value(s) for $α$ is/are

If $P, Q, R$ are subsets of the universal set U, then $$(P\cap Q\cap R) \cup (P^c \cap Q \cap R) \cup Q^c \cup R^c$$ is

$\displaystyle \lim_{x \to \infty}\frac{x-\sin x}{x+\cos x}$ equals

Which of the following statements are true? Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa All $\epsilon$-productions can be removed from any context-free grammar by suitable transformations The language generated by a context-free grammar all of whose productions are of the form $X \rightarrow w$ or …

Consider the following C program that attempts to locate an element $x$ in an array $Y[ \ ]$ using binary search. The program is erroneous. f (int Y[10] , int x) { int i, j, k; i= 0; j = 9; do { k = (i+ j) / 2; if( Y[k] < x) i = k;else j = k; } while (Y[k] != x) && (i < j)) ; if(Y[k] == x) printf(" x is in the array ") ; else printf(" x is …

Consider the following $\text{ER}$ diagram The minimum number of tables needed to represent $M$, $N$, $P$, $R1$, $R2$ is

Consider a file of $16384$ records. Each record is $32\;\text{bytes}$ long and its key field is of size $6\;\text{bytes}$. The file is ordered on a non-key field, and the file organization is unspanned. The file is stored in a file system with block size $1024\;\text{bytes}$, and the size of a block pointer is $10\;\text{bytes}$. If the secondary …

Consider the following segment of C-code: int j, n; j = 1; while (j <= n) j = j * 2; The number of comparisons made in the execution of the loop for any $n > 0$ is:

Consider the following program segment. Here $\text{R1, R2}$ and $\text{R3}$ are the general purpose registers. …

Consider the following program segment. Here $\text{R1, R2}$ and $\text{R3}$ are the general purpose registers. …

Suppose the letters $a, \,b, \,c, \,d, \,e, \,f$ have probabilities $\dfrac{1}{2}, \dfrac{1}{4}, \dfrac{1}{8}, \dfrac{1}{16}, \dfrac{1}{32}, \dfrac{1}{32}$, respectively. What is the average length of the Huffman code for the letters $a, \,b, \,c, \,d, \,e, \,f$?

Consider the following Finite State Automaton: The minimum state automaton equivalent to the above FSA has the following number of states:

Consider the CFG with $\left\{S, A, B\right\}$ as the non-terminal alphabet, $\{a, b\}$ as the terminal alphabet, $S$ as the start symbol and the following set of production rules: $S \rightarrow aB$ $S \rightarrow bA$ $B \rightarrow b$ $A \rightarrow a$ $B \rightarrow bS$ $A \rightarrow aS$ $B \rightarrow aBB$ $A \rightarrow bAA$ For …