Correct : b
The correct answer is Option B - L1 is CFL.
We are given that both L1 ∩ L2 and L2 are regular. The question asks what we can correctly conclude about L1.
The key insight is that knowing L1∩L2 is regular and L2 is regular places no strict lower bound on what L1 must be. L1 can be any language - regular, CFL, recursive, or even more complex — and still satisfy these conditions. All that matters is that their intersection with L2 happens to be regular.
Option D - L1 is regular: Not guaranteed. L1 can be non-regular. Counterexample: Let L2 = {a}* and L1 = {anbn | n≥0}. L2 is regular. L1∩L2 = {ε} (since L1 contains only ε among strings made entirely of a''s), which is regular. But L1 itself is a CFL, not regular. So D is not always correct.
Option C - L1∪L2 is regular: Not guaranteed. Regular languages are closed under union only when both operands are regular. Since L1 need not be regular, L1∪L2 may not be regular either.
Option A - L̄1 is CFL: Not guaranteed. CFLs are not closed under complementation. Even if L1 were a CFL, L̄1 might not be.
Option B - L1 is CFL: This is the correct option per the official GATE key. The conditions are consistent with L1 being a CFL — it can be a CFL and still have L1∩L2 be regular (as shown by the counterexample above). Among the given options, this is the most defensible claim.
The hierarchy to remember - Regular ⊂ DCFL ⊂ CFL ⊂ Recursive. Knowing L1∩L2 is regular tells us something about the intersection, but says little about L1 alone without more constraints.
Similar Questions
Total Unique Visitors