For any two languages L 1 and L 2 such that L 1 is context-free and L 2 is recursively enumerable but not recursive, which of the following is/are necessarily true? I. L̅ 1 (complement of L 1 ) is recursive II. L̅ 2 (complement of L 2 ) is recursive III. L̅ 1 is context-free IV. L̅ 1 ∪ L 2 is recursively enumerable

Correct Answer is : I and IV only

GATE Computer Science (CS) 2015 Shift 1 Solved Paper

Question : 28 of 65

Marks: +1, -0

For any two languages L₁ and L₂ such that L₁ is context-free and L₂ is recursively enumerable but not recursive, which of the following is/are necessarily true?
I. L̅₁ (complement of L₁) is recursive
II. L̅₂ (complement of L₂) is recursive
III. L̅₁ is context-free
IV. L̅₁ ∪ L₂ is recursively enumerable

I only
III only
III and IV only
I and IV only

Validate

Go to Question:

Prev Question

Next Question