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?
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.
Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.
Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.
Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.
Prepare for GATE 2026 Civil Engineering with the latest question papers, previous year papers, detailed solutions, syllabus, exam pattern, preparation tips, mock tests, and subject-wise study material. Download GATE 2026 CE question papers with solutions in PDF format and boost your preparation for top engineering institutes and PSU recruitment.
Prepare effectively for GATE 2026 Electronics & Communication Engineering (EC) with this comprehensive Question Paper with Solutions. This resource includes detailed explanations, concept-wise solutions, previous year paper analysis, and exam-oriented practice to help aspirants strengthen core subjects like Electronic Devices, Analog Circuits, Digital Circuits, Signals & Systems, Network Theory, Control Systems, Electromagnetics, Communications, and more. Perfect for revision, self-assessment, and boosting your GATE 2026 EC preparation strategy.
Copyright © 2026 Combe Labs Private Limited. All Rights Reserved.