GATE CS Theory of Computation questions

Which one of the following is TRUE?

Let $L_1=\{w\in\{0,1\}^*\mid w$ $\text{ has at least as many occurrences of }$ $(110)'\text{s as }$ $(011)'\text{s} \}$. Let $L_2=\{w \in\{0,1\}^*\ \mid w$ $\text{ has at least as many occurrences of }$ $(000)'\text{s as}$ $(111)'\text{s} \}$. Which one of the following is TRUE?

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?

If $L_1\:=\{a^n \mid n\:\geq\:0\}$ and $L_2\:= \{b^n \mid n\:\geq\:0\}$ , consider $L_1.L_2$ is a regular language $L_1.L_2 = \{a^nb^n \mid n\: \geq \:0\}$ Which one of the following is CORRECT?

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

Consider the following languages over the alphabet $\sum = \{0, 1, c\}$ $L_1 = \left\{0^n1^n\mid n \geq 0\right\}$ $L_2 = \left\{wcw^r \mid w \in \{0,1\}^*\right\}$ $L_3 = \left\{ww^r \mid w \in \{0,1\}^*\right\}$ Here, $w^r$ is the reverse of the string $w$. Which of these languages are deterministic Context-free languages?

Which one of the following problems is undecidable?

Let $\Sigma$ be a finite non-empty alphabet and let $2^{\Sigma^*}$ be the power set of $\Sigma^*$. Which one of the following is TRUE?

The length of the shortest string NOT in the language (over $\Sigma = \{a, b\})$ of the following regular expression is _______. $$a^*b^*(ba)^*a^*$$

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)$?

Consider the DFA $A$ given below. Which of the following are FALSE? Complement of $L(A)$ is context-free. $L(A) = L((11^*0+0)(0 + 1)^*0^*1^*)$ For the language accepted by $A, A$ is the minimal DFA. $A$ accepts all strings over $\{0, 1\}$ of length at least $2$.

Consider the following languages. $L_1 = \left \{ 0^p1^q0^r \mid p,q,r \geq 0 \right \}$ $L_2 = \left \{ 0^p1^q0^r \mid p,q,r \geq 0, p\neq r \right \}$ Which one of the following statements is FALSE?

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 statements is/are FALSE? For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine. Turing recognizable languages are closed under union and complementation. Turing decidable languages are closed under intersection and complementation. Turing recognizable languages are closed under union and …

Consider the languages $L_1 = \phi$ and $L_2 = \{a\}$. Which one of the following represents $L_1 {L_2}^* \cup {L_1}^*$ ?

Consider the set of strings on $\{0,1\}$ in which, every substring of $3$ symbols has at most two zeros. For example, $001110$ and $011001$ are in the language, but $100010$ is not. All strings of length less than $3$ are also in the language. A partially completed DFA that accepts this language is shown below. The missing arcs in the DFA are:

Given the language $L = \left\{ab, aa, baa\right\}$, which of the following strings are in $L^{*}$? $abaabaaabaa$ $aaaabaaaa$ $baaaaabaaaab$ $baaaaabaa$

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?

What is the complement of the language accepted by the NFA shown below? Assume $\Sigma = \{a\}$ and $\epsilon$ is the empty string.