GATE CS 1996 Q1.9 — Undecidability

To find the false statement, let us analyze each option based on the decidability properties of formal languages:

• Option A: The Halting Problem of Turing machines is the classic undecidable problem. This statement is true.
• Option B: Determining whether an arbitrary context-free grammar (CFG) is ambiguous is a well-known undecidable problem (reducible from the Post Correspondence Problem). This statement is true.
• Option C: The equivalence problem for CFGs (i.e., determining whether $L(G_1) = L(G_2)$ for two CFGs $G_1$ and $G_2$) is undecidable. This statement is true.
• Option D: Regular grammars generate regular languages. Since regular languages are closed under all boolean operations and have a unique minimal DFA representation, we can easily decide if $L(G_1) = L(G_2)$ by checking if their corresponding minimized DFAs are isomorphic. Thus, the equivalence problem for regular grammars is decidable, making this statement false.

Therefore, the false statement is D.