GATE CS Undecidability questions

​​​​Let $G_{1}, G_{2}$ be Context Free Grammars (CFGs) and $R$ be a regular expression. For a grammar $G$, let $L(G)$ denote the language generated by $G$. Which ONE among the following questions is decidable?

For a Turing machine $M$, $\langle M \rangle$ denotes an encoding of $M$. Consider the following two languages. $$\begin{array}{ll} L_1 = \{ \langle M \rangle \mid M \text{ takes more than } 2021 \text{ steps on all inputs} \} \\ L_2 = \{ \langle M \rangle \mid M\text{ takes more than } 2021 \text{ steps on some input} \} \end{array}$$ Which one of the …

Consider the following problems. $L(G)$ denotes the language generated by a grammar $G$. L(M) denotes the language accepted by a machine $M$. For an unrestricted grammar $G$ and a string $w$, whether $w \in L(G)$ Given a Turing machine $M$, whether $L(M)$ is regular Given two grammar$G_1$ and $G_2$, whether $L(G_1) = L(G_2)$ Given an …

Let $A$ and $B$ be finite alphabets and let $\#$ be a symbol outside both $A$ and $B$. Let $f$ be a total function from $A^{*}$ to $B^{*}$. We say $f$ is computable if there exists a Turing machine $M$ which given an input $x \in A^{*}$, always halts with $f(x)$ on its tape. Let $L_{f}$ denote the language …

Let $L(R)$ be the language represented by regular expression $R$. Let $L(G)$ be the language generated by a context free grammar $G$. Let $L(M)$ be the language accepted by a Turing machine $M$. Which of the following decision problems are undecidable? Given a regular expression $R$ and a string $w$, is $w \in L(R)$? Given a context-free …

Let $X$ be a recursive language and $Y$ be a recursively enumerable but not recursive language. Let $W$ and $Z$ be two languages such that $\overline{Y}$ reduces to $W$, and $Z$ reduces to $\overline{X}$ (reduction means the standard many-one reduction). Which one of the following statements is TRUE?

Which of the following decision problems are undecidable? Given NFAs $N_1$ and $N_2$ , is $L(N_1) \cap L(N_2) = \Phi$ Given a CFG $G = (N,\Sigma,P,S)$ and a string $x \in \Sigma^{*}$, does $x \in L(G)$} ? Given CFGs $G_1$ and $G_2$, is $L (G_1) = L(G_2)$? Given a TM $M$, is $L(M)=\Phi$ ?

Consider the following statements. The complement of every Turing decidable language is Turing decidable There exists some language which is in NP but is not Turing decidable If L is a language in NP, L is Turing decidable Which of the above statements is/are true?

Language $L_1$ is polynomial time reducible to language $L_2$. Language $L_3$ is polynomial time reducible to language $L_2$, which in turn polynomial time reducible to language $L_4$. Which of the following is/are true? $\text{ if } L_4 \in P, \text{ then } L_2 \in P$ $\text{ if } L_1 \in P\text{ or } L_3 \in P, \text{ then } L_2 \in P$ …

Let $L$ be a language and $\bar{L}$ be its complement. Which one of the following is NOT a viable possibility?

Let $\langle M \rangle$ be the encoding of a Turing machine as a string over $\Sigma=\left\{0,1\right\}$. Let $$L=\left\{\langle M \rangle \mid M \text{ is a Turing machine}\\\text{ that accepts a string of length 2014} \right\}.$$ Then $L$ is:

Let $A\:\leq_m\:B$ denotes that language $A$ is mapping reducible (also known as many-to-one reducible) to language $B$. Which one of the following is FALSE?

Consider the decision problem $2CNFSAT$ defined as follows: $$\left\{ \phi \mid \phi \text{ is a satisfiable propositional formula in CNF with at most two literals per clause}\right\}$$ For example, $\phi = (x1 \vee x2) \wedge (x1 \vee \bar{x3}) \wedge (x2 \vee x4)$ is a Boolean formula and it is in $2CNFSAT$. The decision problem $2CNFSAT$ is

Which one of the following problems is undecidable?

Which of the following is/are undecidable? $G$ is a CFG. Is $L(G) = \phi$? $G$ is a CFG. Is $L(G) = \Sigma^*$? $M$ is a Turing machine. Is $L(M)$ regular? $A$ is a DFA and $N$ is an NFA. Is $L(A) = L(N)$?

Which of the following statements are TRUE? The problem of determining whether there exists a cycle in an undirected graph is in $P$. The problem of determining whether there exists a cycle in an undirected graph is in $NP$. If a problem A is $NP-Complete$, there exists a non-deterministic polynomial time algorithm to solve $A$

Which of the following problems are decidable? Does a given program ever produce an output? If $L$ is a context-free language, then, is $\bar{L}$ also context-free? If $L$ is a regular language, then, is $\bar{L}$ also regular? If $L$ is a recursive language, then, is $\bar{L}$ also recursive?

Let $L_1$ be the recursive language. Let $L_2$ and $L_3$ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

Which of the following statements is false?

If $L$ and $\overline{L}$ are recursively enumerable then $L$ is