GATE CSE 2025 Session 2 Q25: Decidable question about context-free grammars

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?

Try it: multiple choice: exactly one correct option

Wrong answer costs 1/3 mark in GATE.

Show answer and explanation

Answer: D (official GATE 2025 final answer key)

Concept used: For CFGs, emptiness and membership are decidable; equivalence, disjointness and equality with a regular set are not.

First step: Emptiness can be checked by marking the generating variables and seeing whether the start symbol is one.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2025 Session 2 CS question paper and final answer key, organised by IIT Roorkee. Question paper · Answer key