GATE CS question library

Consider the following problem $X$. Given a Turing machine $M$ over the input alphabet $\Sigma$, any state $q$ of $M$ and a word $w \in \Sigma^*$, does the computation of $M$ on $w$ visit the state of $q$? Which of the following statements about $X$ is correct?

Consider the following languages: $L1=\left\{ww \mid w \in \{a,b\}^*\right\}$ $L2=\left\{ww^R \mid w \in \{a,b\}^*, w^R \text{ is the reverse of w} \right\}$ $L3=\left\{0^{2i} \mid \text{ i is an integer} \right\}$ $L4= \left\{ 0^{i^2} \mid \text{ i is an integer} \right\}$ Which of the languages are regular?

Consider a DFA over $\Sigma=\{a,b\}$ accepting all strings which have number of a's divisible by $6$ and number of $b$'s divisible by $8$. What is the minimum number of states that the DFA will have?

Let $f: A \rightarrow B$ a function, and let E and F be subsets of $A$. Consider the following statements about images. $S_1: f(E \cup F) = f(E) \cup f(F)$ $S_2: f(E \cap F)=f(E) \cap f(F)$ Which of the following is true about S1 and S2?

How many $4$-digit even numbers have all $4$ digits distinct?

Consider the following statements: $S_1:$ There exists infinite sets $A$, $B$, $C$ such that $A \cap (B \cup C)$ is finite. $S_2:$ There exists two irrational numbers $x$ and y such that $(x+y)$ is rational. Which of the following is true about $S_1$ and $S_2$?

Let r and s be two relations over the relation schemes R and S respectively, and let A be an attribute in R. The relational algebra expression $\sigma_{A=a}(r \bowtie s)$ is always equal to

Which of the following requires a device driver?

Suppose the adjacency relation of vertices in a graph is represented in a table Adj $(X,Y).$ Which of the following queries cannot be expressed by a relational algebra expression of constant length?

Consider a virtual memory system with FIFO page replacement policy. For an arbitrary page access pattern, increasing the number of page frames in main memory will

Which of the following statements is false?

Where does the swap space reside?

The process of assigning load addresses to the various parts of the program and adjusting the code and the data in the program to reflect the assigned addresses is called

Let $f(n) = n^2 \log n$ and $g(n) = n(\log n)^{10}$ be two positive functions of $n$. Which of the following statements is correct?

Consider any array representation of an $n$ element binary heap where the elements are stored from index $1$ to index $n$ of the array. For the element stored at index $i$ of the array $(i \leq n)$, the index of the parent is

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using Randomized quicksort?

A CPU has two modes -- privileged and non-privileged. In order to change the mode from privileged to non-privileged

Given the following karnaugh map, which one of the following represents the minimal Sum-Of-Products of the map?

A processor needs software interrupt to

Suppose a processor does not have any stack pointer registers, which of the following statements is true?