GATE CS 2021 Set 1 Q12 — Regular and Context-free Languages

To determine which language is NOT recursive (i.e., undecidable), we analyze the decidability of each decision problem:

• Option A: Emptiness of a DFA ($L(M) = \emptyset$) is decidable. We can use a simple graph reachability algorithm (like BFS or DFS) to check if any final state is reachable from the start state. Thus, this language is recursive.
• Option B: Completeness of a DFA ($L(M) = \Sigma^*$) is decidable. We can construct the complement DFA and check if its language is empty. Thus, this language is recursive.
• Option C: Emptiness of a PDA ($L(M) = \emptyset$) is decidable. Since PDAs accept context-free languages, we can convert the PDA to a CFG and check if the start symbol can generate any terminal string. Thus, this language is recursive.
• Option D: Completeness of a PDA ($L(M) = \Sigma^*$) is a well-known undecidable (not recursive) problem. It can be shown to be undecidable via reduction from the Turing Machine halting/computation history problem.

Therefore, the language in option D is NOT recursive.