Let L1 and L2 be two languages over a finite alphabet, such that L1∩L2 and L2 are regular. Which of the following statements is/are always true?
Correct Answer :
L2 is context-free
Solution :
The correct option is: L2 is context-free.
Let us analyze the given information:
We are given two languages, L1 and L2, over a finite alphabet, such that:
1. L1 ∩ L2 is regular.
2. L2 is regular.
According to the Chomsky hierarchy of formal languages, there is a strict containment relationship between different classes of languages. Specifically, the class of regular languages is a subset of the class of context-free languages. This relationship can be expressed as:
Since the problem statement explicitly establishes that L2 is a regular language, it mathematically guarantees that L2 is also a context-free language. Therefore, the statement "L2 is context-free" must always be true.
To show why the other statements are not always true, we can consider a counterexample:
Let L2 = ∅ (the empty set), which is a regular language.
Let L1 be any non-context-free language (for example, the copy language ).
In this case, the intersection of the two languages is:
Since the empty set is regular, the condition that L1 ∩ L2 and L2 are regular is satisfied. However, under these conditions:
- L1 is not regular.
- L1 is not context-free.
- L1 ∪ L2 = L1 ∪ ∅ = L1, which is not regular.
This demonstrates that the only statement that is guaranteed to always hold true is that L2 is context-free.
Access expert-curated educational resources and study materials—completely free.
Create, conduct, and manage professional online assessments with Mindyard. Perfect for teachers and institutes.
Copyright © 2026 Mindyard. All Rights Reserved.