Question

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?

• A. Is $L(G_1) = L(G_2)$?
• B. Is $L(G_1) \cap L(G_2) = \emptyset$?
• C. Is $L(G_1) = L(R)$?
• D. Is $L(G_1) = \emptyset$?

Hint:

The problem of determining whether a context-free grammar generates an empty language ($L(G) = \emptyset$) is decidable by checking if the start symbol derives any terminal string. However, checking language equivalence of two CFGs is undecidable.

Answer 1

The Correct Option is D

• (A) Is $L(G_1) = L(G_2)$?
  Checking equivalence of two CFGs is an undecidable problem. There is no general algorithm that can determine whether two context-free grammars (CFGs) generate the same language. This problem is undecidable because determining equivalence would require comparing all possible derivations, which is not computationally feasible for CFGs.
• (B) Is $L(G_1) \cap L(G_2) = \emptyset$?
  The problem of determining whether the intersection of two CFGs is empty is undecidable. While we can check if a single CFG’s language is empty, the intersection of two CFGs does not necessarily form a context-free language, making the problem undecidable. This is because the intersection of two context-free languages may not be context-free, and context-free languages are not closed under intersection.
• (C) Is $L(G_1) = L(R)$?
  The problem of determining whether a context-free language is equal to a regular language is undecidable. There is no algorithm to check whether a CFG generates exactly the same language as a given regular expression. This is because the decision problem involves comparing the generative power of two different classes of languages—context-free languages and regular languages.
• (D) Is $L(G_1) = \emptyset$?
  This problem is decidable. Given a CFG, we can determine whether its language is empty by analyzing its derivation rules and checking if the start symbol can derive any terminal string. This can be done in polynomial time by marking productive non-terminals and checking if the start symbol is productive. If the start symbol is productive, then there is a derivation that produces a string in the language; otherwise, the language is empty.

Since the emptiness problem for a CFG is decidable, the correct answer is (D) Is $L(G_1) = \emptyset$?.