GATE CSE 2025 Set 2 | Push Down Automata and Context Free Language Question 2 | Theory of Computation

GATE CSE 2025 Set 2

MCQ (Single Correct Answer)

-0.33

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?

Is $L\left(G_1\right)=L\left(G_2\right)$ ?

Is $L\left(G_1\right) \cap L\left(G_2\right)=\varnothing$ ?

Is $L\left(G_1\right)=L(R)$ ?

Is $L\left(G_1\right)=\varnothing$ ?

GATE CSE 2025 Set 2

MCQ (More than One Correct Answer)

-0

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

	List - I		List - II
(i)	Context free languages	(a)	Closed under union
(ii)	Recursive languages	(b)	Not closed under complementation
(iii)	Regular languages	(c)	Closed under intersection

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

(i) - (a), (ii) - (b), and (iii) - (c)

(i) - (b), (ii) - (a), and (iii) - (c)

(i) - (b), (ii) - (c), and (iii) - (a)

(i) - (a), (ii) - (c), and (iii) - (b)

GATE CSE 2025 Set 1

MCQ (Single Correct Answer)

-0.33

Consider the following context-free grammar $G$, where $S, A$, and $B$ are the variables (nonterminals), $a$ and $b$ are the terminal symbols, $S$ is the start variable, and the rules of $G$ are described as:

$$\begin{aligned} & S \rightarrow a a B \mid A b b \\ & A \rightarrow a \mid a A \\ & B \rightarrow b \mid b B \end{aligned}$$

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

$L(G)=\left\{a^2 b^n \mid n \geq 1\right\} \cup\left\{a^n b^2 \mid n \geq 1\right\}$

$L(G)=\left\{a^n b^{2 n} \mid n \geq 1\right\} \cup\left\{a^{2 n} b^n \mid n \geq 1\right\}$

$L(G)=\left\{a^n b^n \mid n \geq 1\right\}$

$L(G)=\left\{a^{2 n} b^{2 n} \mid n \geq 1\right\}$

GATE CSE 2021 Set 2

MCQ (More than One Correct Answer)

-0

Let L₁ be a regular language and L₂ be a context-free language. Which of the following languages is/are context-free?

L₁ ∩ L̅₂

L₁ ∪ (L₂ ∪ L̅₂)