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.