GATE 2025 Computer Science Theory of Computation Questions

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:

$S\to aaB\mid Abb$

$A\to a\mid aA$

$B\to b\mid bB$

Which ONE of the languages $L(G)$ is accepted by $G$?

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\}$:

$L_1=\{\alpha \beta \alpha \mid \alpha \in \{a,b{\}}^{+}\text{ AND }\beta \in \{a,b{\}}^{+}\}$

$L_2=\{\alpha \beta \alpha \mid \alpha \in \{a{\}}^{+}\text{ AND }\beta \in \{a,b{\}}^{+}\}$

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.

$L_1=\{a^m{b}^m{c}^{m+n}\mid m,n\ge 1\}$

$L_2=\{a^m{b}^n{c}^{m+n}\mid m,n\ge 1\}$

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)

Which ONE of the following languages is accepted by a deterministic 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:

For matching of items in List I with those in List II, which of the following option(s) is/are CORRECT?

Let $\Sigma =\{a,b,c\}$. For $x\in {\Sigma }^{\ast }$, 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)?

$\Sigma =\{1,2,3,4\}$. For $x\in {\Sigma }^{\ast }$, let $prod(x)$ be the product of symbols in $x$ modulo 7. We take $prod(ϵ)=1$, where $ϵ$ is the null string.

For example, $prod(124)=(1\times 2\times 4)\mathrm{mod}7=1$.

Define $L=\{x\in {\Sigma }^{\ast }\mid prod(x)=2\}$.

The number of states in a minimum state DFA for $L$ is ____________. (Answer in integer)

Consider two grammars $G_1$ and $G_2$ with the production rules given below:

$G_1:S\to ifEthenS|ifEthenSelseS|a$

$E\to b$

$G_2:S\to ifEthenS|M$

$M\to ifEthenMelseS|c$

$E\to b$

where if, then, else, a, b, c are the terminals.

Which of the following option(s) is/are CORRECT?