Let G₁, G₂ be CFGs and R be a regular expression. Which ONE among the following questions is decidable?

Correct Answer: (D) Is L(G₁) = ∅?The Emptiness Problem for CFGs is DECIDABLE: Compute the set of generating non-terminals (those deriving some terminal string). If the start symbol is not generating, L(G) = ∅. This runs in polynomial time.Undecidable CFL problems:Equivalence (A): Is L(G₁) = L(G₂)? — Undecidable.Intersection non-emptiness (B): Is L(G₁) ∩ L(G₂) ≠ ∅? — Undecidable.Equality with regular language (C): Is L(G₁) = L(R)? — Undecidable.

GATE-CS is a competitive examination conducted in India. This question is from the 2025 GATE-CS Theory of Computation paper.

How can I prepare for GATE-CS Theory of Computation?

To prepare for GATE-CS Theory of Computation, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2025 question covers Undecidability topic.

What is the difficulty level of this question?

This GATE-CS 2025 Theory of Computation question has a medium difficulty level and is marked as an important question.

Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

GATE-CS Theory of Computation 2025 - Let G₁, G₂ be CFGs...

Which one of the following statements is equivalent to the following assertion?Turing machine M deci…

EASY2026GATE-CSTheory of Computation

Which of the following is/are undecidable?(A) Given two TMs M1 and M2, decide if L(M1) = L(M2).(B) G…

HARD2022GATE-CSTheory of Computation

Let L1 be a language decidable by a non-deterministic Turing machine in time T(n). Let L2 be a langu…

HARD2021GATE-CSTheory of Computation

Two statements about regular languages: S1: Every infinite regular language contains an undecidable …

HARD2021GATE-CSTheory of Computation

Which of the following languages are undecidable? Note that indicates encoding of the Turing machin…

MEDIUM2020GATE-CSTheory of Computation

Consider sets: S1=Set of all recursively enumerable languages over {0,1}; S2=Set of all syntacticall…

HARD2019GATE-CSTheory of Computation

Let G₁, G₂ be CFGs and R be a regular expression. Which ONE among the following questions is decidable?

Master GATE-CS with Our Test Series

More Questions from Undecidability

Frequently Asked Questions

Let G₁, G₂ be CFGs and R be a regular expression. Which ONE among the following questions is decidable?

Master GATE-CS with Our Test Series

More Questions from Undecidability

Frequently Asked Questions