-
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
-
- I only
- III only
- III and IV only
- I and IV only
- I only
Correct Option: D
I ⇒ L1 is recursive This one is true, because L1 is context free which is nonentity but recursive, recursive language is closed under complement. Hence it is true.
II ⇒ L2 (complement of L2) is recursive If L2 and L2 both are recursive enumerable then L2 is recursive
Hence, statement II is false
III ⇒ L1 is context free Which is false because context free language does not closed under complement.
IV ⇒ L1 L2 is recursive enumerable.
L1 recursive, because every recursive language is also recursive enumerable.
L2 recursive enumerable.
L1 ∪ L2 ⇒ recursive enumerable, because recursive enumerable language closed under union.
