Course contentsShow
← Computer Science
Lesson 1805 of 2,87240. Theory of Computation: Regular LanguagesFree lesson

Closure Properties: Intersection

Regular languages are closed under intersection via product construction of DFAs.

Closure Properties: Intersection

What You'll Learn

You'll discover how to prove that regular languages are closed under intersection by combining two DFAs into a single product DFA.

The Core Idea

Closure under intersection means: if L₁ and L₂ are regular languages, then L₁ ∩ L₂ (the set of strings in both languages) is also regular.

You already know this works! Remember product construction from "Combining Conditions with Product Construction"? That's exactly the technique we use here.

How Product Construction Proves Intersection

Given two DFAs:

  • DFA M₁ recognizing language L₁
  • DFA M₂ recognizing language L₂

We build a new DFA M that simulates both machines simultaneously:

States: Pairs (q₁, q₂) where q₁ is a state from M₁ and q₂ is from M₂

Transitions: On symbol a, move from (q₁, q₂) to (q₁', q₂') where:

  • q₁' is where M₁ goes from q₁ on a
  • q₂' is where M₂ goes from q₂ on a

Accept states: Pairs (q₁, q₂) where both q₁ is accepting in M₁ and q₂ is accepting in M₂

Why It Works

A string reaches an accepting state in M only if it would be accepted by both M₁ and M₂ individually. The product construction tracks both computations in parallel, accepting precisely when both succeed.

Analogy: Imagine two security checkpoints. You pass through the combined system only if you pass both individual checkpoints—that's intersection.

Example Insight

If L₁ = {strings with even length} and L₂ = {strings ending in '1'}, then L₁ ∩ L₂ = {strings with even length and ending in '1'}—still regular, proven by the product DFA.

Key Takeaway: Regular languages are closed under intersection because product construction creates a DFA that accepts only strings accepted by both input DFAs.