Computer Sciences > GATE 2026 SET-1 > Regular Languages
Let L1 and L2 be two languages over a finite alphabet such that L1 ∩ L2 and L2 are Regular. Which of the following is/are correct?
A
1 is CFL
B
L1 is CFL
C
L1 ∪ L2 is regular
D
L1 is regular

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

Let L1, L2 be two regular languages and L3 a language which is not regular. Which of the following statements is/are always TRUE?
#859 MSQ
Which of the following languages is/are regular? L1 = {wxwR | w, x ∈ {a, b}* and |w|, |x| > 0}, wR is the reverse of string w. L2 = {anbm | m ≠ n and...
#1169 MCQ
Let L1 = {w ∈ {0, 1}∗ | w has at least as many occurrences of (110)'s as (011)'s}. Let L2 = {w ∈ {0, 1}∗ | w has at least as many occurrences of (000)'s as (111...
#1268 MCQ

Related Topics

L1 L2 regular language GATE 2026 GATE CS 2026 Set-1 Q23 L1 intersection L2 regular L1 is CFL GATE formal language theory GATE regular closure properties GATE CFL theory of computation L1 union L2 regular GATE computer science 2026

Unique Visitor Count

Total Unique Visitors

Loading......