Question 24

Problem 1: 'Does a given program ever produce an output?'
This is a non-trivial semantic property of program behavior. By Rice's Theorem (or reduction from the Halting Problem), determining whether an arbitrary program produces an output on any input is undecidable.

Problem 2: 'If $L$ is a context-free language, then, is $\overline{L}$ also context-free?'
Context-free languages are not closed under complementation. Determining whether the complement of a given CFL is also context-free is an undecidable problem in formal language theory.

Problem 3: 'If $L$ is a regular language, then, is $\overline{L}$ also regular?'
Regular languages are closed under complementation. For every regular language $L$, its complement $\overline{L}$ is guaranteed to be regular (we can construct a DFA for $\overline{L}$ simply by swapping the accept and non-accept states of the DFA for $L$). Because the statement is unconditionally true for all regular languages, the decision algorithm always answers YES. Hence, Problem 3 is decidable.

Problem 4: 'If $L$ is a recursive language, then, is $\overline{L}$ also recursive?'
Recursive (decidable) languages are closed under complementation. If a Turing machine $M$ halts on all inputs and decides $L$, we construct a decider for $\overline{L}$ by simply inverting the accept and reject states of $M$. Since every recursive language has a recursive complement, the decision algorithm always answers YES. Hence, Problem 4 is decidable.

Thus, problems 3 and 4 are decidable.