GATE CS Theory of Computation questions

Consider the languages: $L_1 = \left\{ a^nb^nc^m \mid n,m >0\right\}$ and $L_2 = \left\{a^nb^mc^m\mid n, m > 0\right\}$ Which one of the following statements is FALSE?

Let $N_f$ and $N_p$ denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let $D_f$ and $D_p$ denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata respectively. 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 …

The following finite state machine accepts all those binary strings in which the number of $1$’s and $0$’s are respectively:

The language $\left\{a^mb^nc^{m+n} \mid m, n \geq1\right\}$ is

Consider the NFA $M$ shown below. Let the language accepted by $M$ be $L$. Let $L_1$ be the language accepted by the NFA $M_1$ obtained by changing the accepting state of $M$ to a non-accepting state and by changing the non-accepting states of $M$ to accepting states. Which of the following statements is true?

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

Let $G=\left(\left\{S\right\}, \left\{a,b\right\},R,S\right)$ be a context free grammar where the rule set R is $S \to a S b \mid S S \mid \epsilon$ Which of the following statements is true?

Consider the following deterministic finite state automaton $M$. Let $S$ denote the set of seven bit binary strings in which the first, the fourth, and the last bits are $1$. The number of strings in $S$ that are accepted by $M$ is

The regular expression $0^*(10^*)^*$ denotes the same set as

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?

The smallest finite automaton which accepts the language $\{x \mid$ length of $x$ is divisible by $3\}$ has

Which of the following is true?

The finite state machine described by the following state diagram with $A$ as starting state, where an arc label is $x/y,$ and $x$ stands for $1$-bit input and $y$ stands for $2$-bit output

The language accepted by a Pushdown Automaton in which the stack is limited to $10$ items is best described as

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?