GATE CS 2017 Set 2 Q41 — Undecidability

To determine which of the decision problems are undecidable, let us analyze each statement individually:

1. Given a regular expression $R$ and a string $w$, is $w \in L(R)$?
   This is the membership problem for regular languages. Since regular languages are closed under all basic operations and have equivalent finite automata (DFA/NFA), we can construct a DFA for $R$ and simulate it on $w$. This process always halts and decides membership.
   Status: Decidable.


2. Given a context-free grammar $G$, is $L(G) = \emptyset$?
   This is the emptiness problem for context-free languages (CFLs). We can decide this by checking if the start symbol of $G$ can generate any terminal string (by systematically identifying and eliminating non-generating variables).
   Status: Decidable.


3. Given a context-free grammar $G$, is $L(G) = \Sigma^*$ for some alphabet $\Sigma$?
   This is the universality problem for CFLs. It is a well-known undecidable problem, which can be proved by showing that the language of invalid computation histories of a Turing machine is context-free. If we could decide whether $L(G) = \Sigma^*$, we could decide the halting problem.
   Status: Undecidable.


4. Given a Turing machine $M$ and a string $w$, is $w \in L(M)$?
   This is the membership problem for Turing machines (often denoted as $A_{TM}$). By Turing's halting problem analysis, there is no algorithm that can decide whether an arbitrary Turing machine $M$ accepts a given input string $w$.
   Status: Undecidable.

Thus, problems III and IV are undecidable.