Question

If L is a recursive language, L’ is:

(a) Recursive

(b) Recursively Ennumerable

(c) Both (a) and (b)

(d) None of the mentioned

This question was addressed to me during an interview for a job.

My question is taken from The Language of Turing Machine-2 in section Introduction to Turing Machines of Automata Theory

Answer 1

The correct choice is (c) Both (a) and (b)

To explain I would say: If T is a turing machine recognizing L, we can make it recognize L’ by interchanging the two outputs. And every recursive language is recursively ennumerable.