Computer Sciences > Gate 2015 Set-1 > CFG
For any two languages L1 and L2 such that L1 is context free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true?
I. L1' (complement of L1) is recursive
II. L2' (complement of L2) is recursive
III. L1' is context-free
IV. L1' ∪ L2 is recursively enumerable
II. L2' (complement of L2) is recursive
III. L1' is context-free
IV. L1' ∪ L2 is recursively enumerable
Explanation
Correct : CFG
Similar Questions
What is the worst-case time complexity of insertion in an AVL tree?
Which operations on a binary search tree have O(h) complexity?
Compare search complexities of sorted array vs balanced BST.