GATE CS 2012 Q24 — Undecidability

A problem is decidable if there exists an algorithm (a Turing machine that halts on all inputs) that can correctly answer "Yes" or "No" for every instance of the problem.

Let us analyze each statement:

1. Does a given program ever produce an output?

   This is a variation of the Halting Problem. Determining whether an arbitrary program produces any output on some input is undecidable (by Rice's Theorem, as it is a non-trivial semantic property of the program).

2. If $L$ is a context-free language, then, is $\bar{L}$ also context-free?

   Context-free languages (CFLs) are not closed under complementation. For a given CFL $L$, its complement $\bar{L}$ may or may not be context-free. Deciding whether the complement of a given CFL is also context-free is an undecidable problem.

3. If $L$ is a regular language, then, is $\bar{L}$ also regular?

   Regular languages are closed under complementation. Therefore, if $L$ is regular, $\bar{L}$ is always regular. Since the answer to this question is always "Yes" for any regular language $L$, the decision problem is trivially decidable (the algorithm simply outputs "Yes").

4. If $L$ is a recursive language, then, is $\bar{L}$ also recursive?

   Recursive (decidable) languages are closed under complementation. If $L$ is recursive, $\bar{L}$ is always recursive. Thus, the answer is always "Yes", making this problem trivially decidable.

Therefore, only problems 3 and 4 are decidable.