Which CFG problem is decidable in GATE CS 2025 Set-2 Q25?

Option D is correct — L(G1)=∅ (CFG emptiness) is decidable. We can check if a CFG generates any string by determining which non-terminals can derive terminal strings. If the start symbol cannot derive any terminal string, the language is empty. This is a standard decidable problem for CFGs.

Why is CFG equivalence L(G1)=L(G2) undecidable?

The equivalence problem for CFGs — whether two CFGs generate the same language — is undecidable. This is proven by reduction from Post's Correspondence Problem or other undecidable problems. Unlike regular languages where DFA minimization allows equivalence checking, CFGs have no such general algorithm.

Why is CFL intersection emptiness L(G1)∩L(G2)=φ undecidable?

The intersection of two CFLs is not always a CFL, and checking whether that intersection is empty is undecidable. This is because CFLs are not closed under intersection, and determining emptiness of a CFL intersection reduces to undecidable problems.

Is checking L(G1)=L(R) decidable for CFG G1 and regular expression R?

No, L(G1)=L(R) is undecidable in general. While checking if a CFL contains a regular language (or is contained in one) has some decidable special cases, full equivalence between a CFL and a regular language is undecidable.

Decidability CFG Regular Language Properties | GATE CS 2025 Set-2 Q25

Computer Sciences > GATE 2025 SET-2 > Decidability

Let G₁, G₂ 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(G₁)=L(G₂)?

Is L(G₁)∩L(G₂)=φ?

Is L(G₁)=L(R)?

Is L(G₁)=∅?

Correct : d

The correct answer is Option D - Is L(G1) = ∅
This question tests knowledge of which problems about context-free grammars are decidable and which are not. Let''s go through each option.
Option A - Is L(G1) = L(G2)? Undecidable. The equivalence problem for two CFGs is a well-known undecidable problem. There is no general algorithm that can determine whether two CFGs generate the same language.
Option B - Is L(G1) ∩ L(G2) = ∅? Undecidable. CFLs are not closed under intersection, and determining whether the intersection of two CFLs is empty is undecidable. It reduces to undecidable problems like Post''s Correspondence Problem.
Option C - Is L(G1) = L(R)? Undecidable. Checking whether a CFL is equal to a given regular language is undecidable in general, even though the regular language itself is simpler.
Option D - Is L(G1) = ∅? Decidable. The emptiness problem for CFGs is decidable. We check which non-terminals in G1 can eventually derive a string of terminals. If the start symbol S cannot derive any terminal string, L(G1) = ∅. This reachability-based algorithm always terminates. Correct.

Similar Questions

Related Topics

Similar Questions

Related Topics

Question Options

Sign in to ExamPrev