GATE CS Theory of Computation questions

Consider the following languages. $L_{1} = \left\{\left\langle M \right\rangle \mid M \text{ takes at least 2016 steps on some input} \right\}$, $L_{2} = \left\{\left\langle M \right\rangle \mid M \text{ takes at least 2016 steps on all inputs} \right\}$ and $L_{3} = \left\{\left\langle M \right\rangle \mid M \ \text{accepts }\epsilon\right\}$, where …

Consider the following two statements: If all states of an NFA are accepting states then the language accepted by the NFA is $\Sigma_{}^{*}$. There exists a regular language $A$ such that for all languages $B$, $A \cap B$ is regular. Which one of the following is CORRECT?

Consider the following types of languages: $L_{1}$: Regular, $L_{2}$: Context-free, $L_{3}$: Recursive, $L_{4}$: Recursively enumerable. Which of the following is/are TRUE ? $\overline{L_{3}} \cup L_{4}$ is recursively enumerable. $\overline{L_{2}} \cup L_{3}$ is recursive. $L^{*} _{1} \cap L_{2}$ is context-free. …

The number of states in the minimum sized DFA that accepts the language defined by the regular expression. $(0+1)^{*} (0+1) (0+1)^{*}$ is ________.

Language $L_{1}$ is defined by the grammar: $S_{1} \rightarrow a S_{1} b \mid \varepsilon$ Language $L_{2}$ is defined by the grammar: $S_{2} \rightarrow a b S_{2} \mid \varepsilon$ Consider the following statements: P: $L_{1}$ is regular Q: $L_{2}$ is regular Which one of the following is TRUE?

Consider the DFAs $M$ and $N$ given above. The number of states in a minimal DFA that accept the language $L(M) \cap L(N)$ is_____________.

Consider the NPDA $$\left \langle Q= \left \{ q_{0}, q_{1}, q_{2} \right \},\Sigma = \left \{ 0, 1 \right \}, \Gamma = \left \{ 0, 1, \perp \right \}, \delta, q_{0}, \perp, F =\left \{ q_{2} \right \} \right \rangle$$, where (as per usual convention) $Q$ is the set of states, $\Sigma$ is the input alphabet, $\Gamma$ is the stack alphabet, $\delta$ is …

For any two languages $L_{1}$ and $L_{2}$ such that $L_{1}$ is context-free and $L_{2}$ is recursively enumerable but not recursive, which of the following is/are necessarily true? $\bar{L}_{1}$ ( Complement of $L_{1}$) is recursive $\bar{L}_{2}$ ( Complement of $L_{2}$) is recursive $\bar{L}_{1}$ is context-free $\bar{L}_{1}$ ∪ $L_{2}$ …

The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.

Which of the following is/are regular languages? $L_1: \left\{ wxw^R \mid w, x \in \{a, b\} ^* \text{ and } |w|, |x| > 0\right\}, w^R \text{ is the reverse of string } w$ $L_2: \left\{ a^nb^m \mid m \neq n \text{ and } m, n \geq 0 \right\}$ $L_3: \left\{ a^pb^qc^r \mid p, q, r \geq 0 \right\}$

Consider the alphabet $\Sigma = \{0, 1\}$, the null/empty string $\lambda$ and the set of strings $X_0, X_1, \text{ and } X_2$ generated by the corresponding non-terminals of a regular grammar. $X_0, X_1, \text{ and } X_2$ are related as follows. $X_0 = 1 X_1$ $X_1 = 0 X_1 + 1 X_2$ $X_2 = 0 X_1 + \{ \lambda \}$ Which one of the following …

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?

Consider two decision problems $Q_1, Q_2$ such that $Q_1$ reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to $Q_2$. Then which one of the following is consistent with the above statement?

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$ …

Which of the following languages are context-free? $L_1: \left\{a^mb^na^nb^m \mid m, n \geq 1\right\}$ $L_2: \left\{a^mb^na^mb^n \mid m, n \geq 1\right\}$ $L_3: \left\{a^mb^n \mid m = 2n +1 \right\}$

Let $L$ be the language represented by the regular expression $\Sigma^*0011\Sigma^*$ where $\Sigma = \{0, 1\}$. What is the minimum number of states in a DFA that recognizes $\bar{L}$ (complement of $L$)?

Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?

Which of the regular expressions given below represent the following DFA? $0^*1(1+00^*1)^*$ $0^*1^*1+11^*0^*1$ $(0+1)^*1$

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

Consider the finite automaton in the following figure: What is the set of reachable states for the input string $0011$?