If L1 ∩L2 and L2 are regular then which of the following is always true?
Solution :
The correct option is: ¯ L2 is CFL
Let us analyze the given conditions and verify why this option is always true step-by-step.
Step 1: Analyze the properties of L2
We are given that L2 is a regular language.
Step 2: Apply the closure properties of regular languages
One of the fundamental closure properties of regular languages is that they are closed under complementation. This means that if a language is regular, its complement is also guaranteed to be regular.
Since L2 is regular, its complement:
is also a regular language.
Step 3: Relationship between Regular Languages and Context-Free Languages (CFLs)
According to the Chomsky hierarchy, the class of regular languages is a strict subset of the class of context-free languages (CFLs). Therefore, every regular language is also a context-free language.
Since the complement of L2 is regular, it must also be a context-free language (CFL).
Step 4: Counterexamples for the other options
To show why the other options are not always true, consider a case where L2 is the empty language (which is regular, i.e., L2 = ∅) and L1 is any non-context-free language (for example, a highly complex non-recursive language).
In this case:
1. The intersection L1 ∩ L2 = L1 ∩ ∅ = ∅, which is regular. This satisfies the problem constraints.
2. However, L1 is not regular, so "L1 is Regular" is false.
3. The complement of L1 (¯ L1) is not a CFL, so "¯ L1 is CFL" is false.
4. The union L1 ∪ L2 = L1 ∪ ∅ = L1, which is not regular, so "L1 ∪ L2 is regular" is false.
Thus, the only statement that is guaranteed to always hold true is that ¯ L2 is a CFL.
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.