Intersection

What is Intersection?

The intersection of two languages L₁ and L₂, denoted L₁ ∩ L₂, is the set of all strings that belong to both L₁ and L₂. It contains only the strings that are common to both languages.

Formal Definition

L₁ ∩ L₂ = {w | w ∈ L₁ and w ∈ L₂}

A string is in the intersection if and only if it appears in both languages.

Simple Analogy

Think of intersection like finding common elements:

Set A: {Alice, Bob, Charlie}
Set B: {Bob, Charlie, David}
Intersection: {Bob, Charlie} (people in both sets)

In languages, we find strings that exist in both languages.

Basic Examples

Example 1: Simple Finite Languages

L₁ = {a, b, c}
L₂ = {b, c, d}

L₁ ∩ L₂ = {b, c}

Only ‘b’ and ‘c’ are in both languages.

Example 2: Disjoint Languages

L₁ = {0, 00}
L₂ = {1, 11}

L₁ ∩ L₂ = ∅

No common strings, so intersection is empty.

Example 3: One is Subset

L₁ = {a, b}
L₂ = {a, b, c, d}

L₁ ∩ L₂ = {a, b} = L₁

When L₁ ⊆ L₂, then L₁ ∩ L₂ = L₁

Example 4: Identical Languages

L₁ = {0, 1, 01}
L₂ = {0, 1, 01}

L₁ ∩ L₂ = {0, 1, 01} = L₁ = L₂

Example 5: With Empty String

L₁ = {ε, a, aa}
L₂ = {ε, b, bb}

L₁ ∩ L₂ = {ε}

Only ε is common.

Example 6: Intersection with Empty Language

L = {a, b, c}

L ∩ ∅ = ∅

Intersection with empty language is always empty.

Example 7: Intersection with Universal Language

Σ = {0, 1}
L = {0, 01, 001}

L ∩ Σ* = L

Intersection with Σ* gives back the original language.

Infinite Language Examples

Example 1: Even and Odd Length

Σ = {0, 1}
L₁ = {w | |w| is even}
L₂ = {w | |w| is odd}

L₁ ∩ L₂ = ∅

No string can have both even and odd length!

Example 2: Starting and Ending Conditions

Σ = {0, 1}
L₁ = {w | w starts with 0}
L₂ = {w | w ends with 1}

L₁ ∩ L₂ = {w | w starts with 0 AND ends with 1}
         = {01, 001, 011, 0001, 0011, 0101, 0111, ...}

Example 3: Specific Patterns

Σ = {a, b}
L₁ = {aⁿbⁿ | n ≥ 0} = {ε, ab, aabb, aaabbb, ...}
L₂ = {w | |w| is even}

L₁ ∩ L₂ = {aⁿbⁿ | n is even}
         = {ε, aabb, aaaabbbb, ...}

Example 4: Multiple Constraints

Σ = {0, 1}
L₁ = {w | w contains "00"}
L₂ = {w | w contains "11"}

L₁ ∩ L₂ = {w | w contains both "00" and "11"}
         = {0011, 1100, 00011, 00110, 01100, 11000, ...}

Properties of Intersection

1. Commutativity

Order doesn’t matter:

L₁ ∩ L₂ = L₂ ∩ L₁

Example:

L₁ = {a, b}, L₂ = {b, c}
L₁ ∩ L₂ = {b}
L₂ ∩ L₁ = {b} ✓

2. Associativity

Grouping doesn’t matter:

(L₁ ∩ L₂) ∩ L₃ = L₁ ∩ (L₂ ∩ L₃)

Example:

L₁ = {a, b, c}
L₂ = {b, c, d}
L₃ = {c, d, e}

(L₁ ∩ L₂) ∩ L₃ = {b, c} ∩ {c, d, e} = {c}
L₁ ∩ (L₂ ∩ L₃) = {a, b, c} ∩ {c, d} = {c} ✓

3. Identity Element

The universal language Σ* is the identity:

L ∩ Σ* = L

Example:

L = {0, 1}
L ∩ Σ* = {0, 1} = L ✓

4. Absorbing Element

Empty language absorbs everything:

L ∩ ∅ = ∅

5. Idempotent

Intersection with itself gives same language:

L ∩ L = L

6. Subset Relationship

L₁ ∩ L₂ ⊆ L₁
L₁ ∩ L₂ ⊆ L₂

Intersection is always a subset of both languages.

7. Monotonicity

If L₁ ⊆ L₂, then L₁ ∩ L₃ ⊆ L₂ ∩ L₃

Size of Intersection

For finite languages:

|L₁ ∩ L₂| ≤ min(|L₁|, |L₂|)

Intersection cannot be larger than the smaller language.

Examples:

L₁ = {a, b, c}, L₂ = {b, c}
|L₁| = 3, |L₂| = 2
|L₁ ∩ L₂| = |{b, c}| = 2 ≤ min(3, 2) = 2 ✓

L₁ = {0, 1}, L₂ = {2, 3}
|L₁ ∩ L₂| = |∅| = 0 ≤ min(2, 2) = 2 ✓

Relationship with Union

Distributive Laws:

L₁ ∩ (L₂ ∪ L₃) = (L₁ ∩ L₂) ∪ (L₁ ∩ L₃)
L₁ ∪ (L₂ ∩ L₃) = (L₁ ∪ L₂) ∩ (L₁ ∪ L₃)

Example:

L₁ = {a, b}
L₂ = {a}
L₃ = {b}

L₁ ∩ (L₂ ∪ L₃) = {a, b} ∩ {a, b} = {a, b}
(L₁ ∩ L₂) ∪ (L₁ ∩ L₃) = {a} ∪ {b} = {a, b} ✓

Absorption Laws:

L₁ ∪ (L₁ ∩ L₂) = L₁
L₁ ∩ (L₁ ∪ L₂) = L₁

De Morgan’s Laws

Very important for exams!

Law 1:

(L₁ ∪ L₂)̄ = L̄₁ ∩ L̄₂

Complement of union = Intersection of complements

Law 2:

(L₁ ∩ L₂)̄ = L̄₁ ∪ L̄₂

Complement of intersection = Union of complements

Example:

Σ = {0, 1}
L₁ = {0}
L₂ = {00}

L₁ ∩ L₂ = ∅
(L₁ ∩ L₂)̄ = ∅̄ = Σ*

L̄₁ = all except "0" = {ε, 1, 00, 01, 10, 11, 000, ...}
L̄₂ = all except "00" = {ε, 0, 1, 01, 10, 11, 000, ...}
L̄₁ ∪ L̄₂ = Σ* ✓

Expressing Intersection Using Other Operations

Intersection can be expressed using complement and union:

L₁ ∩ L₂ = (L̄₁ ∪ L̄₂)̄

Or using complement and difference:

L₁ ∩ L₂ = L₁ - (L₁ - L₂)

This is important because some automata models (like CFGs) are not closed under intersection, but we can sometimes work around it.

Closure Properties

Regular Languages: ✓ Closed under intersection

If L₁ and L₂ are regular, then L₁ ∩ L₂ is regular.

Context-Free Languages: ✗ NOT closed under intersection

Example: L₁ = {aⁿbⁿcᵐ | n, m ≥ 0} (CFL)
         L₂ = {aᵐbⁿcⁿ | m, n ≥ 0} (CFL)
         L₁ ∩ L₂ = {aⁿbⁿcⁿ | n ≥ 0} (NOT CFL!)

Note: CFLs ARE closed under intersection with regular languages.

Constructing DFA for Intersection

For regular languages, we can construct a DFA for L₁ ∩ L₂:

Method: Product Construction

Start with DFA M₁ for L₁ and DFA M₂ for L₂
Create product DFA with states (q₁, q₂) for each q₁ in M₁ and q₂ in M₂
Accepting states: Both q₁ and q₂ are accepting
Transitions: δ((q₁, q₂), a) = (δ₁(q₁, a), δ₂(q₂, a))

Example:

M₁ accepts strings ending in '0'
M₂ accepts strings of even length

M₁ ∩ M₂ accepts strings of even length ending in '0'
Examples: 0, 00, 10, 0000, 0100, 1010, ...

Practical Applications

1. Multiple Constraints

valid_users = authenticated ∩ authorized ∩ not_banned

2. Pattern Matching

L₁ = {strings containing "error"}
L₂ = {strings from log file}

error_logs = L₁ ∩ L₂

L₁ = {documents containing "machine learning"}
L₂ = {documents containing "neural networks"}

results = L₁ ∩ L₂ (both topics)

4. Access Control

allowed = (has_permission) ∩ (within_time_window) ∩ (valid_location)

Intersection with Complement

Intersection and complement can express set difference:

L₁ - L₂ = L₁ ∩ L̄₂

Example:

L₁ = {a, b, c}
L₂ = {b}

L₁ - L₂ = {a, c}

L̄₂ = all except {b}
L₁ ∩ L̄₂ = {a, c} ✓

Multiple Intersections

Intersecting multiple languages:

L₁ ∩ L₂ ∩ L₃ = {w | w ∈ L₁ AND w ∈ L₂ AND w ∈ L₃}

Example:

Σ = {0, 1}
L₁ = {w | w starts with 0}
L₂ = {w | w ends with 1}
L₃ = {w | |w| is even}

L₁ ∩ L₂ ∩ L₃ = {w | starts with 0, ends with 1, even length}
               = {01, 0001, 0011, 0101, 0111, 000001, ...}

Important Identities

L ∩ Σ* = L (identity)
L ∩ ∅ = ∅ (absorbing)
L ∩ L = L (idempotent)
L₁ ∩ L₂ = L₂ ∩ L₁ (commutative)
(L₁ ∩ L₂) ∩ L₃ = L₁ ∩ (L₂ ∩ L₃) (associative)
L ∩ L̄ = ∅ (intersection with complement)
(L₁ ∩ L₂)̄ = L̄₁ ∪ L̄₂ (De Morgan)
L₁ ∩ (L₂ ∪ L₃) = (L₁ ∩ L₂) ∪ (L₁ ∩ L₃) (distributive)
L₁ ∩ L₂ ⊆ L₁ and L₁ ∩ L₂ ⊆ L₂ (subset)
L₁ - L₂ = L₁ ∩ L̄₂ (difference)

Important Exam Points

✓ Intersection: L₁ ∩ L₂ = {w | w ∈ L₁ AND w ∈ L₂}
✓ Commutative: L₁ ∩ L₂ = L₂ ∩ L₁
✓ Associative: (L₁ ∩ L₂) ∩ L₃ = L₁ ∩ (L₂ ∩ L₃)
✓ Identity: L ∩ Σ* = L
✓ Absorbing: L ∩ ∅ = ∅
✓ Idempotent: L ∩ L = L
✓ L ∩ L̄ = ∅ (disjoint with complement)
✓ Regular languages closed under intersection
✓ CFLs NOT closed under intersection (important!)
✓ De Morgan: (L₁ ∩ L₂)̄ = L̄₁ ∪ L̄₂
✓ |L₁ ∩ L₂| ≤ min(|L₁|, |L₂|)

Common Mistakes to Avoid

❌ Mistake 1: L₁ ∩ L₂ = {w₁w₂ | w₁ ∈ L₁, w₂ ∈ L₂}
✓ Correct: That’s concatenation, not intersection!

❌ Mistake 2: Intersection makes larger language
✓ Correct: L₁ ∩ L₂ ⊆ L₁ and L₁ ∩ L₂ ⊆ L₂

❌ Mistake 3: L ∩ ∅ = L
✓ Correct: L ∩ ∅ = ∅

❌ Mistake 4: (L₁ ∩ L₂)̄ = L̄₁ ∩ L̄₂
✓ Correct: (L₁ ∩ L₂)̄ = L̄₁ ∪ L̄₂ (De Morgan)

❌ Mistake 5: CFLs are closed under intersection
✓ Correct: CFLs are NOT closed under intersection

❌ Mistake 6: {a, b} ∩ {c, d} = {a, b, c, d}
✓ Correct: {a, b} ∩ {c, d} = ∅ (disjoint sets)

Practice Questions

Q1: Find L₁ ∩ L₂ where L₁ = {a, ab, abc} and L₂ = {ab, abc, abcd}.

Answer: L₁ ∩ L₂ = {ab, abc}

Q2: What is L ∩ ∅?

Answer: L ∩ ∅ = ∅ (for any language L)

Q3: If L₁ = {w | |w| is even} and L₂ = {w | |w| is odd}, what is L₁ ∩ L₂?

Answer: L₁ ∩ L₂ = ∅ (no string can be both even and odd length)

Q4: Is intersection commutative? Give an example.

Answer: Yes. L₁ = {a}, L₂ = {a, b}
L₁ ∩ L₂ = {a} = L₂ ∩ L₁

Q5: Express L₁ - L₂ using intersection and complement.

Answer: L₁ - L₂ = L₁ ∩ L̄₂

Q6: Are regular languages closed under intersection?

Answer: Yes, regular languages are closed under intersection.

Q7: Are context-free languages closed under intersection?

Answer: No, CFLs are NOT closed under intersection.

Q8: Apply De Morgan’s Law to (L₁ ∩ L₂)̄.

Answer: (L₁ ∩ L₂)̄ = L̄₁ ∪ L̄₂

Summary

Intersection (L₁ ∩ L₂) contains strings in both languages
Requires string to satisfy all conditions
Commutative and associative
Identity: Σ* (universal language)
Absorbing: ∅ (empty language)
Always a subset of both languages
Regular languages closed under intersection
CFLs NOT closed under intersection (important exception!)
Can be computed using product construction for DFAs
Used for multiple constraints, search refinement
De Morgan’s Laws relate intersection to union and complement

Intersection is essential for combining multiple conditions and is a fundamental operation in automata theory and formal language theory!

Intersection

What is Intersection?

Formal Definition

Simple Analogy

Basic Examples

Example 1: Simple Finite Languages

Example 2: Disjoint Languages

Example 3: One is Subset

Example 4: Identical Languages

Example 5: With Empty String

Example 6: Intersection with Empty Language

Example 7: Intersection with Universal Language

Infinite Language Examples

Example 1: Even and Odd Length

Example 2: Starting and Ending Conditions

Example 3: Specific Patterns

Example 4: Multiple Constraints

Properties of Intersection

1. Commutativity

2. Associativity

3. Identity Element

4. Absorbing Element

5. Idempotent

6. Subset Relationship

7. Monotonicity

Size of Intersection

Examples:

Relationship with Union

Distributive Laws:

Absorption Laws:

De Morgan’s Laws

Law 1:

Law 2:

Expressing Intersection Using Other Operations

Closure Properties

Constructing DFA for Intersection

Method: Product Construction

Practical Applications

1. Multiple Constraints

2. Pattern Matching

3. Search Refinement

4. Access Control

Intersection with Complement

Multiple Intersections

Important Identities

Important Exam Points

Common Mistakes to Avoid

Practice Questions

Summary

Install Notes App