GATE CS question library

Consider the set of integers $\{1,2,3,4,6,8,12,24\}$ together with the two binary operations LCM (lowest common multiple) and GCD (greatest common divisor). Which of the following algebraic structures does this represent?

Which of the following three statements are true? Prove your answer.

The access times of the main memory and the Cache memory, in a computer system, are $500$ n sec and $50$ nsec, respectively. It is estimated that $80\%$ of the main memory request are for read the rest for write. The hit ratio for the read access only is $0.9$ and a write-through policy (where both main and cache memories are updated simultaneously) …

Start and stop bits do not contain any "information" but are used in serial communication for

In which of the cases stated below is the following statement true? "For every non-deterministic machine $M_{1}$ there exists an equivalent deterministic machine $M_{2}$ recognizing the same language".

Which of the following regular expression identities is/are TRUE?

Which of the following is/are a tautology?

Context-free languages are:

If $G$ is a context free grammar and $w$ is a string of length $l$ in $L(G)$, how long is a derivation of $w$ in $G$, if $G$ is in Chomsky normal form?

Consider the $\text{SLR(1)}$ and $\text{LALR (1)}$ parsing tables for a context free grammar. Which of the following statement is/are true?

For a context free grammar, FOLLOW(A) is the set of terminals that can appear immediately to the right of non-terminal $A$ in some "sentential" form. We define two sets LFOLLOW(A) and RFOLLOW(A) by replacing the word "sentential" by "left sentential" and "right most sentential" respectively in the definition of FOLLOW (A).

Which of the following is an example of a spooled device?

A computer system has $6$ tape devices, with n processes competing for them. Each process may need $3$ tape drives. The maximum value of n for which the system is guaranteed to be deadlock-free is:

At a particular time of computation, the value of a counting semaphore is $7$. Then $20$ $P$ operations and $15$ $V$ operations were completed on this semaphore. The resulting value of the semaphore is :

A non-planar graph with minimum number of vertices has

A $2-3$ tree is such that All internal nodes have either $2$ or $3$ children All paths from root to the leaves have the same length The number of internal nodes of a $2-3$ tree having $9$ leaves could be

Which of the following problems is not $\text{NP}$-hard?

Start and stop bits do not contain any 'information' but are used in serial communication

Following algorithm(s) can be used to sort $n$ in the range $[1\ldots n^3]$ in $O(n)$ time

The operation which is commutative but not associative is: