Recent questions tagged gate1992

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 memor...

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?$2l$$2l +1$$2l -1$$...

Which of the following regular expression identities is/are TRUE?$r^{(^\ast)} =r^\ast$$(r^\ast s^\ast)=(r+s)^\ast$$(r+s)^\ast = r^\ast + s^\ast$$r^\ast s^\ast = r^\ast+s^...

Which of the following is/are a tautology?$a \vee b \to b \wedge c$$a \wedge b \to b \vee c$$a \vee b \to \left(b \to c \right)$$a \to b \to \left(b \to c \right)$

Context-free languages are:closed under unionclosed under complementationclosed under intersectionclosed under Kleene closure

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

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 L...

Which of the following is an example of a spooled device?The terminal used to input data for a program being executed.The secondary memory device in a virtual memory syst...

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 guarant...

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 resu...

A $2-3$ tree is such thatAll internal nodes have either $2$ or $3$ childrenAll paths from root to the leaves have the same lengthThe number of internal nodes of a $2-3$ t...

Which of the following problems is not $\text{NP}$-hard?Hamiltonian circuit problemThe $0/1$ Knapsack problemFinding bi-connected components of a graphThe graph coloring ...

Start and stop bits do not contain any 'information' but are used in serial communicationError detectionError correctionSynchronizationSlowing down the communications

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

All digital circuits can be realized using onlyEx-OR gatesMultiplexersHalf addersOR gates

The operation which is commutative but not associative is:ANDOREX-ORNAND

Maximum number of edges in a planar graph with $n$ vertices is _____

In an $11$-bit computer instruction format, the size of address field is $4$-bits. The computer uses expanding OP code technique and has $5$ two-address instructions and ...

A simple and reliable data transfer can be accomplished by using the 'handshake protocol'. It accomplishes reliable data transfer because for every data item sent by the ...

Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing $n$ vertices and $m$ edges if the edges are sorted is _______

Many of the advanced microprocessors prefetch instructions and store it in an instruction buffer to speed up processing. This speed up is achieved because ________

Many microprocessors have a specified lower limit on clock frequency (apart from the maximum clock frequency limit) because _____

Consider a $3$-bit error detection and $1$-bit error correction hamming code for $4$-bit data. The extra parity bits required would be _____ and the $3$-bit error detecti...

The Boolean function in sum of products form where K-map is given below (figure) is _______

Which of the following predicate calculus statements is/are valid?$(\forall (x)) P(x) \vee (\forall(x))Q(x) \implies (\forall (x)) (P(x) \vee Q(x))$$(\exists (x)) P(x) \w...