-
Define languages L0 and L1 as follows
L0 = {< M, W, 0 > |M halts on W}
L1 = {
Here < M, W, i > is a triplet, whose first component, M is an encoding of a turing machine, second component W is a string and third component i is a bit.
Let L = L0 ∪ L1 . Which of the following is true?
-
- L is recursively enumerable, but L is not
- L is recursively enumerable, but L is not
- Both L and L are recursive
- Neither L nor L is recursively enumerable
- L is recursively enumerable, but L is not
Correct Option: A
If L0 ∪ L1 is recursively enumerable, it means we can find out for all W ∈ ∑*, where M halts or does not halt. This means that if L0 ∪ L1 is recursively enumerable, the halting problem would be decidable. But we know, the halting problem is undecidable.
Therefore L = L0 ∪ L1 is not RE.
Since, L = (L0 ∪ L1)c = L0c ∩ L1c = φ which is regular language and hence is RE.
Therefore, L is RE. So, correct option is (b), which is L is RE but L is not.
