GATE CS Undecidability questions

Which of the following are decidable? Whether the intersection of two regular languages is infinite Whether a given context-free language is regular Whether two push-down automata accept the same language Whether a given grammar is context-free

Which of the following problems is undecidable?

Consider the following two problems on undirected graphs: $\alpha$: Given $G(V, E)$, does $G$ have an independent set of size |V| - $4$? $\beta$: Given $G(V, E)$, does $G$ have an independent set of size $5$? Which one of the following is TRUE?

Let $L_1$ be a recursive language, and let $L_2$ be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

Consider three decision problems $P_1$, $P_2$ and $P_3$. It is known that $P_1$ is decidable and $P_2$ is undecidable. Which one of the following is TRUE?

$L_1$ is a recursively enumerable language over $\Sigma$. An algorithm $A$ effectively enumerates its words as $\omega_1, \omega_2, \omega_3, \dots .$ Define another language $L_2$ over $\Sigma \cup \left\{\text{\#}\right\}$ as $\left\{w_i \text{\#} w_j \mid w_i, w_j \in L_1, i < j \right\}$. Here # is new symbol. Consider the following …

A single tape Turing Machine $M$ has two states $q0$ and $q1$, of which $q0$ is the starting state. The tape alphabet of $M$ is $\{0, 1, B\}$ and its input alphabet is $\{0, 1\}$. The symbol $B$ is the blank symbol used to indicate end of an input string. The transition function of $M$ is described in the following table. …

Nobody knows yet if $P=NP$. Consider the language $L$ defined as follows.$$L = \begin{cases} (0+1)^* & \text{ if } P = NP \\ \phi & otherwise \end{cases}$$Which of the following statements is true?

Consider two languages $L_1$ and $L_2$ each on the alphabet $\Sigma$. Let $f : \Sigma^* \to \Sigma^*$ be a polynomial time computable bijection such that $(\forall x) [ x\in L_1$ iff $f(x) \in L_2]$. Further, let $f^{-1}$ be also polynomial time computable. Which of the following CANNOT be true?

Define languages $L_0$ and $L_1$ as follows : $L_0 = \{\langle M, w, 0 \rangle \mid M \text{ halts on }w\}$ $L_1 = \{\langle M, w, 1 \rangle \mid M \text{ does not halts on }w\}$ Here $\langle M, w, i \rangle$ is a triplet, whose first component $M$ is an encoding of a Turing Machine, second component $w$ is a string, and third component $i$ …

If the strings of a language $L$ can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?

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 decision problems: $(P1):$ Does a given finite state machine accept a given string? $(P2):$ Does a given context free grammar generate an infinite number of strings? Which of the following statements is true?

Which one of the following is not decidable?

Which of the following statements is false?

It is undecidable whether:

Which of the following problems are undecidable?