Question

If a language $L$ and its complement $L'$ are both Recursively Enumerable (RE), then $L$ is:

• A. Context-sensitive
• B. Recursive
• C. Not accepted by any Turing Machine
• D. Universal

Hint:

Complement Laws: The class of Recursive languages is closed under complementation, but the class of Recursively Enumerable (RE) languages is NOT.

Answer 1

The Correct Option is B

Concept: Languages are categorized based on whether a Turing Machine (TM) can accept them or decide them.
• Recursively Enumerable (RE): A TM will halt and accept if the string is in $L$, but may loop forever if it is not.
• Recursive (Decidable): A TM will always halt, either accepting or rejecting.

Step 1: Analyzing the property of RE languages.
If $L$ is RE, we have a machine $M_1$ that halts on strings in $L$. If $L'$ is also RE, we have another machine $M_2$ that halts on strings NOT in $L$.

Step 2: Constructing a Decider.
We can run $M_1$ and $M_2$ in parallel (interleaving their steps). For any input $w$, it must be either in $L$ or in $L'$. This means either $M_1$ or $M_2$ is guaranteed to halt eventually.

Step 3: Defining Recursive.
Since we can now guarantee a "Halt" for every single input, the language is Decidable. In formal language theory, a Decidable language is called a Recursive language.