Question

Which of the following problems are decidable?
1. Does a given program ever produce an output?
2. If L is a context-free language,then, is $\overline{L}$ also context-free?
3. If L is a regular language,then,is $\overline{L}$ also regular
4. If L is a recursive language,then,is $\overline{L}$ also recursive

Answer 1

Statement (1) is undecidable (since it is the halting problem of TM).
Complement of a context free language, may or may not be context free. So statement number (2) is not only a non trival problem but is also
undecidable.
If L is regualr, $\overline{L}$ is surely regular.
So statement number(3) is (trivially) decidable.
Also if L is recursive, $\overline{L}$,is also surely recursive.
So statement number (4) is also (trivially) decidable.
So. correct option is (d) i.e.only 3 and 4 are decidable.