Project ForgeFor 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. L̄1 (complement of L1) is recursive II. L̄2 (complement of L2) is recursive III. L̄1 is context-free IV. L̄1 ∪ L2 is recursively enumerable
- AI only
- BIII only
- CIII and IV only
- I and IV only
Explanation
L1 being context-free implies L1 is recursive (CFLs are decidable), and recursive languages are closed under complement, so L̄1 is recursive — I is TRUE. If L̄2 were recursive, then L2 (its complement) would also be recursive, contradicting that L2 is not recursive — so II is FALSE. CFLs are NOT closed under complement in general, so III is not necessarily true. L̄1 is recursive (hence r.e.), and the union of two r.e. languages is r.e., so L̄1∪L2 is r.e. — IV is TRUE. So I and IV only.
Source: GATE CS 2015 (Session 1 / 7th Feb Shift 1) (2015)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.