Home › Previous year questions › GATE 2025 CS (CS2) › Question 25GATE 2025 CS (CS2) – Question 25 Theory of Computation · Turing Machines and Undecidability · 1 mark · Multiple choice
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?
Is $L(G_1) = L(G_2)$? Is $L(G_1) \cap L(G_2) = \emptyset$? Is $L(G_1) = L(R)$? Is $L(G_1) = \emptyset$? Practise this question in The GATE Grind →
Show answer and explanation Correct answer: (D) Is $L(G_1) = \emptyset$?
Explanation Emptiness of a CFG is decidable by checking whether the start symbol is productive. Equivalence of CFGs, emptiness of the intersection of two CFLs, and equality of a CFL with a regular language are all undecidable.
More Turing Machines and Undecidability questions GATE 2022 CS Q46 – Which of the following is/are undecidable? GATE 2021 CS (CS1) Q22 – Let M denote an encoding of an automaton M. Suppose that = \0,1\. Which of the following… GATE 2021 CS (CS1) Q49 – For a Turing machine M, M denotes an encoding of M. Consider the following two languages.… GATE 2020 CS Q36 – Which of the following languages are undecidable? Note that M indicates encoding of the… GATE 2019 CS Q44 – Consider the following sets: S1. Set of all recursively enumerable languages over the… GATE 2018 CS Q17 – The set of all recursively enumerable languages is All Turing Machines and Undecidability questions →