If L and L¯ are recursively enumerable, then L is
A)Regular
B)Context free
C)Context sensitive
D)Recursive

Question

Quizplus · Accepted Answer

If both a language L and its complement L¯ are recursively enumerable, then L is recursive. This is because a recursive language is one for which there exists a Turing machine that will halt on all inputs, either accepting or rejecting them. If both L and its complement are recursively enumerable, it means there are Turing machines that can list all the members of L and all the members of L¯, respectively. Therefore, one can decide membership in L by running both Turing machines in parallel and seeing which one accepts the input, ensuring the process will always halt.

If L and L¯ Are Recursively Enumerable, Then L Is