Project ForgeConsider the following types of languages: L1: Regular, L2: Context-free, L3: Recursive, L4: Recursively enumerable. Which of the following is/are TRUE?
I. L̄3∪L4 is recursively enumerable II. L̄2∪L3 is recursive III. L1*∩L2 is context-free IV. L1∪L̄2 is context-free
- AI only
- BI and III only
- CI and IV only
- I, II and III only
Explanation
I: L3 recursive ⟹ L̄3 recursive ⟹ r.e.; union with r.e. L4 stays r.e. TRUE. II: L2 context-free ⟹ recursive (decidable) ⟹ L̄2 recursive (closed under complement); union of two recursive sets is recursive. TRUE. III: regular closed under Kleene star, and CFL∩regular is always CFL (standard closure property). TRUE. IV: CFLs are NOT closed under complement in general, so L̄2 need not be context-free — this one is NOT always true. So I, II and III only.
Source: GATE CS 2016 (Session 2 / Set B) (2016)
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.