GATE CS question library

Which of the following well-formed formulas are equivalent?

Context-free languages and regular languages are both closed under the operation (s) of :

An unrestricted use of the "go to" statement is harmful because of which of the following reason (s):

In which of the following case(s) is it possible to obtain different results for call-by-reference and call-by-name parameter passing?

A hash table with ten buckets with one slot per bucket is shown in the following figure. The symbols $S1$ to $S7$ initially entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an item that is not present is

What is printed by following program, assuming call-by reference method of passing parameters for all variables in the parameter list of procedure P? program Main(inout, output); var a, b:integer; procedure P(x, y, z:integer); begin y:=y+1 z:=x+x end P; begin a:=2; b:=3; p(a+b, a, a); Write(a) end.

Define the value of $r$ in the following: $\sqrt {(41)_{r}} = (7)_{10}$

A Boolean function $f$ is to be realized only by $\text{NOR}$ gates. Its $K$-map is given below: The realization is

The below figure shows four $\text{D}$-type flip-flops connected as a shift register using a $\text{XOR}$ gate. The initial state and three subsequent states for three clock pulses are also given. …

The Boolean expression $A \oplus B \oplus A$ is equivalent to

State whether the following statements are TRUE or FALSE: A relation $r$ with schema $(X, Y)$ satisfies the function dependency $X \rightarrow Y$, The tuples $\langle 1, 2\rangle$ and $\langle 2, 2 \rangle$ can both be in $r$ simultaneously.

State whether the following statements are TRUE or FALSE: The problem as to whether a Turing machine $M$ accepts input $w$ is undecidable.

State whether the following statement are TRUE or FALSE. $A$ is recursive if both $A$ and its complement are accepted by Turing machines.

State whether the following statements are TRUE or FALSE: The intersection of two CFL's is also a CFL.

State whether the following statements are TRUE or FALSE: A minimal DFA that is equivalent to an NDFA with $n$ nodes has always $2^{n}$ states.

State whether the following statements are TRUE or FALSE: Regularity is preserved under the operation of string reversal.

State whether the following statements are TRUE or FALSE: All subsets of regular sets are regular.

State whether the following statements are TRUE or FALSE: If the number of leaves in a tree is not a power of $2,$ then the tree is not a binary tree.

State whether the following statements are TRUE or FALSE: The union of two equivalence relations is also an equivalence relation.

State whether the following statements are TRUE or FALSE: It is possible to construct a binary tree uniquely whose pre-order and post-order traversals are given?