Question Details

If L1 ∩L2 and L2 are regular then which of the following is always true?

Options

A

¯ L1 is CFL

B

L1 is Regular

C

L1 ∪ L2 is regular

D

¯ L2 is CFL

Show Answer
Correct Answer
D
¯ L2 is CFL

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:
L2¯
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.

Transparent Access on Mindyard

Built for Learners & Educators Alike

Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.

FREE FOR STUDENTS

Practice & Learn Free for Students

Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.

  • Unlimited mock tests & question bank practice
  • Full access to curated study library & formula notes
  • 100% free for students • No credit card required
2 MONTHS FREE TRIAL

Educators & Coaching Institutes

Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.

  • AI question uploader & rapid test generator
  • Anti-cheating tab proctoring & performance reports
  • Full Pro access free for 60 days • No upfront commitment
Discover more resources

You may also like

Mock Tests

View All
  • GATE
  • beginner
  • 3 hours
  • civil engineering

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.

  • GATE
  • beginner
  • 3 hours
  • electronics and communication engineering

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.

Ask AI Tutor
5 left
Q1 View Question & Options
AI Tutor is solving this question...
Reading question context & options...
Ask your own doubt or choose a quick prompt: