Which of the following statements is false?

Concept: Decidability splits along the type of grammar. Regular languages (regular grammars, NFAs, DFAs) are closed under complement and intersection, so their standard questions, including whether two regular grammars generate the same language, are decidable: convert each grammar to a minimal DFA and test whether the symmetric difference is empty. Context-free grammars do not admit this construction — CFLs are not closed under complement or intersection — and several natural CFG questions are, in fact, proven undecidable by reduction from the Post Correspondence Problem (PCP's undecidability transfers to CFG ambiguity and to CFG-to-CFG language equivalence). The Halting Problem for Turing machines is the foundational undecidable problem underlying these reductions.

Application: checking each statement by its own claim:

• “The Halting Problem of Turing machines is undecidable” is true. This is the foundational undecidability result; no algorithm can decide, for every machine-input pair, whether the machine halts.

• “Determining whether a context-free grammar is ambiguous is undecidable” is true. There is no general algorithm that decides ambiguity for an arbitrary CFG; this is proved by reduction from the Post Correspondence Problem.

• “Given two arbitrary context-free grammars G1 and G2, it is undecidable whether L(G1) = L(G2)” is true. This is a classical undecidability result: an algorithm that could decide CFG language equality could be used to decide instances of the Post Correspondence Problem, which is itself undecidable — so no such algorithm can exist.

• “Given two regular grammars G1 and G2, it is undecidable whether L(G1) = L(G2)” is false. Regular languages are closed under complement and intersection, so equivalence of two regular grammars reduces to checking whether the symmetric difference of the corresponding minimal DFAs accepts the empty language, a decidable, algorithmic test.

Cross-check: regular-language properties — emptiness, membership, and equivalence — are uniformly decidable, which is why the regular-grammar equivalence claim above does not hold as an undecidability result. For context-free grammars specifically, membership and emptiness ARE decidable; it is ambiguity and language equivalence — the two CFG properties this item asks about — that are undecidable, by the classical results cited above. So exactly one of the four statements breaks the ‘undecidable’ pattern shared by the other three: the claim that regular-grammar equivalence is undecidable is false, since regular-language equivalence is precisely one of the decidable cases.