GATE CS Theory of Computation questions

Consider the following grammar where $S$ is the start symbol, and $a$ and $b$ are terminal symbols. $$S \rightarrow a S b S \text{ | } b S \text{ | } \epsilon$$ Which of the following statements is/are true?

Let $M$ be a nondeterministic finite automaton (NFA) with $6$ states over a finite alphabet. Which of the following options CANNOT be the number of states in the minimal deterministic finite automaton (DFA) that is equivalent to $M$ ?

Let $L_{1}$ and $L_{2}$ be two languages over a finite alphabet, such that $L_{1} \cap L_{2}$ and $L_{2}$ are regular languages. Which of the following statements is/are always true?

Consider the following context-free grammar $G$. $$\begin{array}{l} S \rightarrow a b a A B A b b a \\ A \rightarrow a a B B A b \mid b B a b a a \\ B \rightarrow a B b \mid a b \end{array}$$ In the above grammar, $S$ is the start symbol, $a$ and $b$ are terminal symbols, and $A$ and $B$ are non-terminal symbols. Let $L(G)$ be the language …

Which one of the following statements is equivalent to the following assertion? Turing machine $M$ decides the language $L \subseteq\{0,1\}^{*}$

Consider the following two finite automata $D_{1}$ and $D_{2}$. Which of the following statements is/are true?

Let $\Sigma=\{a, b, c, d\}$ and let $L=\left\{a^{i} b^{j} c^{k} d^{\ell} \mid i, j, k, \ell \geq 0\right\}$. Which of the following constraints ensure(s) that the language $L$ is context-free?

Consider the following context-free grammar $G$, where $S, A$, and $B$ are the variables (non-terminals), $a$ and $b$ are the terminal symbols, $S$ is the start variable, and the rules of $G$ are described as: $$\begin{array}{l} S \rightarrow a a B \mid A b b \\ A \rightarrow a \mid a A \\ B \rightarrow b \mid b B \end{array}$$ Which ONE of the …

A regular language $L$ is accepted by a non-deterministic finite automaton (NFA) with $n$ states. Which of the following statement(s) is/are FALSE?

Consider the following two languages over the alphabet $\{a, b\}$: $$\begin{array}{l} L_{1}=\left\{\alpha \beta \alpha \mid \alpha \in\{a, b\}^{+} \text{AND } \beta \in\{a, b\}^{+}\right\} \\ L_{2}=\left\{\alpha \beta \alpha \mid \alpha \in\{a\}^{+} \text{AND } \beta \in\{a, b\}^{+}\right\} \end{array}$$ Which ONE of the following statements is CORRECT?

Consider the following two languages over the alphabet $\{a, b, c\}$, where $m$ and $n$ are natural numbers. $$\begin{aligned} L_{1} & =\left\{a^{m} b^{m} c^{m+n} \mid m, n \geq 1\right\} \\ L_{2} & =\left\{a^{m} b^{n} c^{m+n} \mid m, n \geq 1\right\} \end{aligned}$$ Which ONE of the following statements is CORRECT?

Consider the following deterministic finite automaton (DFA) defined over the alphabet, $\Sigma=\{a, b\}$. Identify which of the following language(s) is/are accepted by the given DFA.

Consider a finite state machine (FSM) with one input $X$ and one output $f$, represented by the given state transition table. The minimum number of states required to realize this FSM is _______. (Answer in integer). …

Let $\Sigma=\{a, b, c\}$. For $x \in \Sigma^{*}$, and $\alpha \in \Sigma$, let $\#_{\alpha}(x)$ denote the number of occurrences of $\alpha$ in $x$. Which one or more of the following option(s) define(s) regular language(s)?

Let $\Sigma=\{1,2,3,4\}$. For $x \in \Sigma^{*}$, let $\operatorname{prod}(x)$ be the product of symbols in $x$ modulo 7. We take $\operatorname{prod}(\epsilon)=1$, where $\epsilon$ is the null string. For example, $\operatorname{prod}(124)=(1 \times 2 \times 4) \bmod 7=1$. Define …

​​​​Which ONE of the following languages is accepted by a deteministic pushdown automaton?

​​​​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?

Consider the two lists List I and List II given below: …

​Let $L_1, L_2$ be two regular languages and $L_3$ a language which is not regular. Which of the following statements is/are always TRUE?

​Consider the $5$ -state $\text{DFA}$. $M$ accepting the language $L(M) \subset(0+1)^{*}$ shown below. For any string $w \in(0+1)^*$ let $n_0(w)$ be the number of $0^{\prime} s$ in $w$ and $n_1(w)$ be the number of 1 's in $w$. Which of the following statements is/are FALSE?